代码

#include <pthread.h>
#include <string.h>

typedef unsigned u32;

enum { MAXN = 10000005, THREADS = 4 };

typedef struct {
    int id;
    int input_begin, input_end;
} Worker;

static u32 tree[THREADS][MAXN] __attribute__((aligned(4096)));
static u32 order_[MAXN] __attribute__((aligned(4096)));
static int part[THREADS + 1];
static Worker workers[THREADS];
static pthread_barrier_t barrier;
static const u32 *xs, *ys;
static u32 *answers;
static int size_;

static __attribute__((always_inline)) inline u32 query(const u32 *bit, u32 y) {
    u32 answer = 0;
    for (u32 i = y; i; i &= i - 1) answer += bit[i - 1];
    return answer;
}

static __attribute__((always_inline)) inline void insert(u32 *bit, u32 y,
                                                          u32 n) {
    for (u32 i = y; i < n; i |= i + 1) ++bit[i];
}

static void *run(void *argument) {
    Worker *worker = argument;
    const int id = worker->id;
    const int n = size_;
    u32 *bit = tree[id];

#ifdef LOCAL
    memset(bit, 0, (size_t)n * sizeof(*bit));
#endif
    for (int i = worker->input_begin; i < worker->input_end; ++i)
        ++bit[xs[i]];
    pthread_barrier_wait(&barrier);

    if (id == 0) {
        u32 total = 0;
        for (int x = 0; x < n; ++x) {
            u32 c0 = tree[0][x], c1 = tree[1][x];
            u32 c2 = tree[2][x], c3 = tree[3][x];
            tree[0][x] = total;
            tree[1][x] = total + c0;
            tree[2][x] = total + c0 + c1;
            tree[3][x] = total + c0 + c1 + c2;
            total += c0 + c1 + c2 + c3;
        }
    }
    pthread_barrier_wait(&barrier);

    for (int i = worker->input_begin; i < worker->input_end; ++i)
        order_[tree[id][xs[i]]++] = (u32)i;
    pthread_barrier_wait(&barrier);

    if (id == 0) {
        part[0] = 0;
        part[THREADS] = n;
        for (int t = 1; t < THREADS; ++t) {
            int p = (int)(((unsigned long long)n * t) / THREADS);
            while (p < n && p > 0 && xs[order_[p]] == xs[order_[p - 1]]) ++p;
            part[t] = p;
        }
    }
    pthread_barrier_wait(&barrier);

    memset(bit, 0, (size_t)n * sizeof(*bit));
    int begin = part[id], end = part[id + 1];
    for (int p = 0; p < begin; ++p) ++bit[ys[order_[p]]];
    for (u32 i = 0; i < (u32)n; ++i) {
        u32 parent = i | (i + 1);
        if (parent < (u32)n) bit[parent] += bit[i];
    }

    for (int first = begin; first < end;) {
        u32 x = xs[order_[first]];
        int last = first + 1;
        while (last < end && xs[order_[last]] == x) ++last;
        for (int p = first; p < last; ++p) {
            u32 point = order_[p];
            answers[point] = query(bit, ys[point]);
        }
        for (int p = first; p < last; ++p) {
            u32 point = order_[p];
            insert(bit, ys[point], (u32)n);
        }
        first = last;
    }
    return 0;
}

void count_2d(int n, const u32 *x, const u32 *y, u32 *out) {
    pthread_t threads[THREADS - 1];
    size_ = n; xs = x; ys = y; answers = out;
    pthread_barrier_init(&barrier, 0, THREADS);
    for (int t = 0; t < THREADS; ++t) {
        workers[t].id = t;
        workers[t].input_begin = (int)(((unsigned long long)n * t) / THREADS);
        workers[t].input_end = (int)(((unsigned long long)n * (t + 1)) / THREADS);
    }
    for (int t = 1; t < THREADS; ++t)
        pthread_create(&threads[t - 1], 0, run, &workers[t]);
    run(&workers[0]);
    for (int t = 1; t < THREADS; ++t) pthread_join(threads[t - 1], 0);
    pthread_barrier_destroy(&barrier);
}

评测结果