代码

// Problem 1008: 2D dominance, n=1e7. Radix-CDQ v4: descending-y trick (no batching).
// 8-bit lockstep sort by x -> per-group descending-y sort -> d1 (top12 Fenwick, single pass)
// -> 2-pass perm by top12 -> d2 (low12 Fenwick, single pass) fused with out scatter.
#include <cstring>
typedef unsigned u32; typedef unsigned long long u64;

static u64 keys[10000000];
static u64 tkey[10000000];
static u32 ysort[10000000];
static u32 tysort[10000000];
static u32 ans[10000000];
static u32 ans2[10000000];
static u32 cnt[4097];
static u32 fen[4098];

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    // 1. 8-bit lockstep sort by x (3 passes)
    for (int i = 0; i < n; i++) { keys[i] = (u64)x[i] | ((u64)(unsigned)i << 32); ysort[i] = y[i]; }
    u64 *a = keys, *b = tkey; u32 *ya = ysort, *yb = tysort;
    for (int shift = 0; shift < 24; shift += 8) {
        for (int i = 0; i < 256; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[(a[i] >> shift) & 255]++;
        for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
        for (int i = n - 1; i >= 0; i--) { u32 p = --cnt[(a[i] >> shift) & 255]; b[p] = a[i]; yb[p] = ya[i]; }
        u64 *t = a; a = b; b = t; u32 *ty = ya; ya = yb; yb = ty;
    }
    if (a != keys) { memcpy(keys, a, (size_t)n * 8); memcpy(ysort, ya, (size_t)n * 4); }

    // 2. per-x-group sort by y DESCENDING
    int k = 0;
    while (k < n) {
        u32 cx = (u32)(keys[k] & 0xFFFFFFFFu);
        int kk = k + 1;
        while (kk < n && (u32)(keys[kk] & 0xFFFFFFFFu) == cx) kk++;
        int g = kk - k;
        if (g == 2) {
            u32 y0 = ysort[k], y1 = ysort[k + 1];
            if (y0 < y1) { ysort[k] = y1; ysort[k + 1] = y0; u64 tk = keys[k]; keys[k] = keys[k + 1]; keys[k + 1] = tk; }
        } else if (g > 2) {
            for (int i = k + 1; i < kk; i++) {
                u32 yv = ysort[i]; u64 kv = keys[i];
                int j = i - 1;
                while (j >= k && ysort[j] < yv) { ysort[j + 1] = ysort[j]; keys[j + 1] = keys[j]; j--; }
                ysort[j + 1] = yv; keys[j + 1] = kv;
            }
        }
        k = kk;
    }

    // 3. d1: Fenwick over top12, single pass
    memset(fen, 0, sizeof(fen));
    for (int t = 0; t < n; t++) {
        u32 yp = ysort[t] >> 12; u32 s = 0;
        for (u32 j = yp; j; j &= j - 1) s += fen[j];
        ans[t] = s;
        for (u32 j = yp + 1; j <= 4096; j += j & -j) fen[j]++;
    }

    // 4. 2-pass perm by top12 (8-bit then 4-bit)
    for (int i = 0; i < 256; i++) cnt[i] = 0;
    for (int t = 0; t < n; t++) cnt[(ysort[t] >> 12) & 255]++;
    for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
    for (int t = n - 1; t >= 0; t--) { u32 p = --cnt[(ysort[t] >> 12) & 255]; tysort[p] = ysort[t]; tkey[p] = keys[t]; ans2[p] = ans[t]; }
    for (int i = 0; i < 16; i++) cnt[i] = 0;
    for (int t = 0; t < n; t++) cnt[(tysort[t] >> 20) & 15]++;
    for (int i = 1; i < 16; i++) cnt[i] += cnt[i-1];
    for (int t = n - 1; t >= 0; t--) { u32 p = --cnt[(tysort[t] >> 20) & 15]; ysort[p] = tysort[t]; keys[p] = tkey[t]; ans[p] = ans2[t]; }

    // 5. d2: Fenwick over low12, single pass, fused out scatter
    memset(fen, 0, sizeof(fen));
    int cb = -1;
    for (int t = 0; t < n; t++) {
        u32 yy = ysort[t];
        int bucket = (int)(yy >> 12);
        if (bucket != cb) { memset(fen, 0, sizeof(fen)); cb = bucket; }
        u32 yl = yy & 4095; u32 s = 0;
        for (u32 jj = yl; jj; jj &= jj - 1) s += fen[jj];
        out[(u32)(keys[t] >> 32)] = ans[t] + s;
        for (u32 jj = yl + 1; jj <= 4096; jj += jj & -jj) fen[jj]++;
    }
}

评测结果