代码

// Problem 1008: 2D dominance. radix2idx (2-pass) + gather y + 2-level Fenwick B=32.
typedef unsigned u32; typedef unsigned long long u64;

static u64 keys[10000000];
static u64 temp[10000000];
static int cnt16[65536];
static unsigned ysort[10000000];
static u32 topFen[320000];
static u32 botFen[10000064];

static void radix2x(int n) {
    u64 *a = keys, *b = temp;
    for (int shift = 0; shift < 32; shift += 16) {
        for (int i = 0; i < 65536; i++) cnt16[i] = 0;
        for (int i = 0; i < n; i++) cnt16[(a[i] >> shift) & 0xFFFF]++;
        for (int i = 1; i < 65536; i++) cnt16[i] += cnt16[i-1];
        for (int i = n-1; i >= 0; i--) b[--cnt16[(a[i] >> shift) & 0xFFFF]] = a[i];
        u64 *t = a; a = b; b = t;
    }
    if (a != keys) {
        for (int i = 0; i < n; i++) keys[i] = a[i];
    }
}

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    for (int i = 0; i < n; i++) keys[i] = (u64)x[i] | ((u64)(unsigned)i << 32);
    radix2x(n);
    for (int k = 0; k < n; k++) ysort[k] = y[(int)(keys[k] >> 32)];

    const int lgB = 5, B = 32, mask = 31;
    int NB = n >> lgB;
    int k = 0;
    while (k < n) {
        u32 cur_x = (u32)(keys[k] & 0xFFFFFFFFu);
        int kk = k + 1;
        while (kk < n && (u32)(keys[kk] & 0xFFFFFFFFu) == cur_x) kk++;
        for (int t = k; t < kk; ++t) {
            u32 yy = ysort[t];
            u32 b = yy >> lgB, c = yy & mask;
            u32 s = 0;
            for (u32 j = b; j; j &= j - 1) s += topFen[j];
            u32 base = b << lgB;
            for (u32 j = c; j; j &= j - 1) s += botFen[base + j];
            out[(int)(keys[t] >> 32)] = s;
        }
        for (int t = k; t < kk; ++t) {
            u32 yy = ysort[t];
            u32 b = yy >> lgB, c = yy & mask;
            u32 base = b << lgB;
            for (u32 j = c + 1; j <= (u32)B; j += j & -j) botFen[base + j]++;
            for (u32 j = b + 1; j <= (u32)NB; j += j & -j) topFen[j]++;
        }
        k = kk;
    }
}

评测结果