代码

typedef unsigned int u32;
typedef unsigned long U;

#ifndef CAPACITY
#define CAPACITY 10005
#endif
enum { MAXN = CAPACITY };

typedef struct {
    u32 x, y, z, id;
} Point;

static Point point[MAXN];
static int index_[MAXN], temp_index[MAXN];
static int order_[MAXN], merge_buffer[MAXN];
static int count_[MAXN], bit[MAXN], touched[MAXN];
static int touched_count;
static u32 *answer;

static __attribute__((always_inline)) inline void bit_add(int n, u32 z) {
    for (int i = (int)z + 1; i <= n; i += i & -i)
        if (bit[i]++ == 0) touched[touched_count++] = i;
}

static __attribute__((always_inline)) inline u32 bit_query(u32 z) {
    u32 sum = 0;
    for (int i = (int)z; i; i -= i & -i) sum += (u32)bit[i];
    return sum;
}

static void cdq(int n, int l, int r) {
    if (r - l <= 1 || point[l].x == point[r - 1].x) return;

    int mid = (l + r) >> 1;
    u32 split_x = point[mid].x;
    while (mid > l && point[mid - 1].x == split_x) --mid;
    if (mid == l) {
        mid = (l + r) >> 1;
        split_x = point[mid - 1].x;
        while (mid < r && point[mid].x == split_x) ++mid;
    }

    cdq(n, l, mid);
    cdq(n, mid, r);

    int i = l;
    touched_count = 0;
    for (int j = mid; j < r; ++j) {
        int q = order_[j];
        while (i < mid && point[order_[i]].y < point[q].y) {
            bit_add(n, point[order_[i]].z);
            ++i;
        }
        answer[point[q].id] += bit_query(point[q].z);
    }
    for (int k = 0; k < touched_count; ++k) bit[touched[k]] = 0;

    i = l;
    int j = mid, p = l;
    while (i < mid && j < r) {
        if (point[order_[i]].y <= point[order_[j]].y)
            merge_buffer[p++] = order_[i++];
        else
            merge_buffer[p++] = order_[j++];
    }
    while (i < mid) merge_buffer[p++] = order_[i++];
    while (j < r) merge_buffer[p++] = order_[j++];
    for (p = l; p < r; ++p) order_[p] = merge_buffer[p];
}

void count_3d(int n, const u32 *x, const u32 *y, const u32 *z, u32 *out) {
    answer = out;
    for (int i = 0; i < n; ++i) {
        index_[i] = i;
        out[i] = 0;
        count_[i] = 0;
        bit[i + 1] = 0;
    }

    for (int i = 0; i < n; ++i) ++count_[y[i]];
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int c = count_[i];
        count_[i] = sum;
        sum += c;
    }
    for (int i = 0; i < n; ++i) temp_index[count_[y[i]]++] = i;

    for (int i = 0; i < n; ++i) count_[i] = 0;
    for (int i = 0; i < n; ++i) ++count_[x[temp_index[i]]];
    sum = 0;
    for (int i = 0; i < n; ++i) {
        int c = count_[i];
        count_[i] = sum;
        sum += c;
    }
    for (int i = 0; i < n; ++i) {
        int id = temp_index[i];
        index_[count_[x[id]]++] = id;
    }

    for (int i = 0; i < n; ++i) {
        int id = index_[i];
        point[i] = (Point){x[id], y[id], z[id], (u32)id};
        order_[i] = i;
    }
    cdq(n, 0, n);
}

#ifndef LOCAL
static char **initial_argv;
static U initial_argc;

U getauxval(U key) {
    char **p = initial_argv + initial_argc + 1;
    while (*p) ++p;
    U *aux = (U *)(p + 1);
    while (aux[0]) {
        if (aux[0] == key) return aux[1];
        aux += 2;
    }
    return 0;
}

__attribute__((noreturn))
void __libc_start_main(int (*entry)(int, char **, char **), int argc,
                       char **argv) {
    initial_argc = (U)argc;
    initial_argv = argv;
    entry(argc, argv, (char **)0);
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall"
                     ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}
#endif

评测结果