代码

// Problem 1008: 2D dominance (n=1e7). Counting sort by x -> gather -> 2-level Fenwick (B=256).
#include <cstring>
typedef unsigned u32;

static int cnt[10000000];
static int order[10000000];
static unsigned ysort[10000000];
static int idxsort[10000000];
static unsigned xsort[10000000];
static u32 topFen[40000];
static u32 botFen[10000003];

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    // counting sort by x
    for (int i = 0; i < n; ++i) cnt[x[i]]++;
    for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; ++i) order[--cnt[x[i]]] = i;
    // gather contiguous
    for (int k = 0; k < n; ++k) {
        int ii = order[k];
        ysort[k] = y[ii]; idxsort[k] = ii; xsort[k] = x[ii];
    }
    // sweep: 2-level Fenwick (B=256)
    int NB = n >> 8;
    int k = 0;
    while (k < n) {
        unsigned cur_x = xsort[k];
        int kk = k + 1;
        while (kk < n && xsort[kk] == cur_x) kk++;
        for (int t = k; t < kk; ++t) {
            u32 yy = ysort[t];
            u32 b = yy >> 8, c = yy & 255;
            u32 s = 0;
            for (u32 j = b; j; j &= j - 1) s += topFen[j];
            u32 base = b << 8;
            for (u32 j = c; j; j &= j - 1) s += botFen[base + j];
            out[idxsort[t]] = s;
        }
        for (int t = k; t < kk; ++t) {
            u32 yy = ysort[t];
            u32 b = yy >> 8, c = yy & 255;
            u32 base = b << 8;
            for (u32 j = c + 1; j <= 256; j += j & -j) botFen[base + j]++;
            for (u32 j = b + 1; j <= (u32)NB; j += j & -j) topFen[j]++;
        }
        k = kk;
    }
}

评测结果