代码

// task-80 / noi17int tb2: tb1 (tri-state bitsets) + a single uniform-run overlay.
//
// tb1 (tbi.cpp) is 2-3x faster than v31 on normal shapes but pays O(run/64) bitset
// words on every whole-run fill/clear, which the m13/m14 long-run family repeats
// hundreds of thousands of times.  tb2 keeps the tb1 fast path untouched and adds
// ONE overlay interval {cL,cR,cV}: words in [cL,cR] are uniform cV and the bitsets
// + W are STALE there.  Everything (getWord/putWord/find/range) is overlay-aware.
//
//   rangeZeros/Ones(l,r): if the range covers the overlay -> just move/keep it O(1);
//                         if it is long (>= T words) -> flush + set overlay O(1);
//                         else flush any overlap + raw bitset update.
//   putWord inside the overlay: shrink it from the touched END (O(1), this is what
//                         the alternating-end pattern needs); strictly interior ->
//                         flush (O(run/64), same order as v31's flush).
//   findNotOnes(f): overlay all-ones -> skip past cR; overlay all-zeros -> answer is
//                         the first word of the overlay.  (cache-aware find: the
//                         task-65/66 bug was a find that saw only one mechanism.)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <sys/auxv.h>
#include <immintrin.h>
#pragma GCC target("avx2")

typedef uint64_t u64;
typedef uint32_t u32;

enum { NBITS = 30000000 };
enum { NW = NBITS / 64 + 64 };
enum { NWB = (NW + 63) / 64 };
enum { CACHE_T = 1024 };                 // words: overlay threshold

static u64 W[NW];
static u64 NO[NWB], NZ[NWB];

static int cL = 1, cR = 0;              // empty overlay when cL > cR
static u64 cV = 0;
static inline bool inCache(int w) { return (unsigned)(w - cL) < (unsigned)(cR - cL + 1); }

// ---------------- raw (overlay-blind) bitset ops ----------------
static void rawZeros(int l, int r) {
    if (l > r) return;
    int wl = l >> 6, wr = r >> 6;
    u64 ml = ~0ULL << (l & 63), mr = ~0ULL >> (63 - (r & 63));
    if (wl == wr) { u64 m = ml & mr; NO[wl] |= m; NZ[wl] &= ~m; return; }
    NO[wl] |= ml; NZ[wl] &= ~ml;
    NO[wr] |= mr; NZ[wr] &= ~mr;
    if (wl + 1 <= wr - 1) {
        int n = wr - wl - 1, i = wl + 1;
        if (n <= 4) { for (; i < wr; i++) { NO[i] = ~0ULL; NZ[i] = 0ULL; } }
        else { memset(NO + i, 0xff, (size_t)n * 8); memset(NZ + i, 0x00, (size_t)n * 8); }
    }
}
static void rawOnes(int l, int r) {
    if (l > r) return;
    int wl = l >> 6, wr = r >> 6;
    u64 ml = ~0ULL << (l & 63), mr = ~0ULL >> (63 - (r & 63));
    if (wl == wr) { u64 m = ml & mr; NO[wl] &= ~m; NZ[wl] |= m; return; }
    NO[wl] &= ~ml; NZ[wl] |= ml;
    NO[wr] &= ~mr; NZ[wr] |= mr;
    if (wl + 1 <= wr - 1) {
        int n = wr - wl - 1, i = wl + 1;
        if (n <= 4) { for (; i < wr; i++) { NO[i] = 0ULL; NZ[i] = ~0ULL; } }
        else { memset(NO + i, 0x00, (size_t)n * 8); memset(NZ + i, 0xff, (size_t)n * 8); }
    }
}
static inline void flushCache() {
    if (cL > cR) return;
    if (cV == ~0ULL) rawOnes(cL, cR); else rawZeros(cL, cR);
    cL = 1; cR = 0;
}
static void rangeZeros(int l, int r) {
    if (l > r) return;
    if (cL <= cR && l <= cL && r >= cR) {             // new range covers the overlay:
        cL = l; cR = r; cV = 0ULL; return;            // no flush needed (its bits are dead)
    }
    if (cL <= cR && !(r < cL || l > cR)) flushCache();// partial overlap: materialise
    if (r - l + 1 >= CACHE_T) { flushCache(); cL = l; cR = r; cV = 0ULL; return; }
    rawZeros(l, r);
}
static void rangeOnes(int l, int r) {
    if (l > r) return;
    if (cL <= cR && l <= cL && r >= cR) {
        cL = l; cR = r; cV = ~0ULL; return;
    }
    if (cL <= cR && !(r < cL || l > cR)) flushCache();
    if (r - l + 1 >= CACHE_T) { flushCache(); cL = l; cR = r; cV = ~0ULL; return; }
    rawOnes(l, r);
}

// ---------------- word access ----------------
static inline u64 getWord(int w) {
    if (inCache(w)) return cV;
    int wi = w >> 6; u64 b = 1ULL << (w & 63);
    if (!(NO[wi] & b)) return ~0ULL;
    if (!(NZ[wi] & b)) return 0ULL;
    return W[w];
}
static inline void putWord(int w, u64 v) {
    if (inCache(w)) {
        if (w == cL) { cL++; }
        else if (w == cR) { cR--; }
        else if (w - cL <= cR - w) {                  // materialise the smaller side
            if (cV == ~0ULL) rawOnes(cL, w - 1); else rawZeros(cL, w - 1);
            cL = w + 1;
        } else {
            if (cV == ~0ULL) rawOnes(w + 1, cR); else rawZeros(w + 1, cR);
            cR = w - 1;
        }
    }
    int wi = w >> 6; u64 b = 1ULL << (w & 63);
    if (v == ~0ULL)      { NO[wi] &= ~b; NZ[wi] |=  b; }
    else if (v == 0)     { NO[wi] |=  b; NZ[wi] &= ~b; }
    else                 { NO[wi] |=  b; NZ[wi] |=  b; W[w] = v; }
}

// ---------------- overlay-aware search ----------------
static inline int scanNO(int w, int hi) {
    if (w > hi) return -1;
    int wi = w >> 6, s = w & 63, whi = hi >> 6;
    u64 x = NO[wi] & (~0ULL << s);
    if (wi == whi) x &= (~0ULL >> (63 - (hi & 63)));
    if (x) return (wi << 6) + __builtin_ctzll(x);
    // AVX2: test four plane words (256 x-words) per iteration, and only fall back
    // to the scalar ctz in the 4-word group that is actually non-zero.
    int i = wi + 1;
    __m256i zero = _mm256_setzero_si256();
    for (; i + 3 < whi; i += 4) {
        __m256i v = _mm256_loadu_si256((const __m256i *)(NO + i));
        if (!_mm256_testz_si256(v, v)) {
            for (int k = 0; k < 4; k++) { u64 y = NO[i + k]; if (y) return ((i + k) << 6) + __builtin_ctzll(y); }
        }
    }
    for (; i <= whi; i++) {
        u64 y = NO[i];
        if (i == whi) y &= (~0ULL >> (63 - (hi & 63)));
        if (y) return (i << 6) + __builtin_ctzll(y);
    }
    return -1;
}
static inline int scanNZ(int w, int hi) {
    if (w > hi) return -1;
    int wi = w >> 6, s = w & 63, whi = hi >> 6;
    u64 x = NZ[wi] & (~0ULL << s);
    if (wi == whi) x &= (~0ULL >> (63 - (hi & 63)));
    if (x) return (wi << 6) + __builtin_ctzll(x);
    // AVX2: test four plane words (256 x-words) per iteration, and only fall back
    // to the scalar ctz in the 4-word group that is actually non-zero.
    int i = wi + 1;
    __m256i zero = _mm256_setzero_si256();
    for (; i + 3 < whi; i += 4) {
        __m256i v = _mm256_loadu_si256((const __m256i *)(NZ + i));
        if (!_mm256_testz_si256(v, v)) {
            for (int k = 0; k < 4; k++) { u64 y = NZ[i + k]; if (y) return ((i + k) << 6) + __builtin_ctzll(y); }
        }
    }
    for (; i <= whi; i++) {
        u64 y = NZ[i];
        if (i == whi) y &= (~0ULL >> (63 - (hi & 63)));
        if (y) return (i << 6) + __builtin_ctzll(y);
    }
    return -1;
}
// first j >= w whose word is NOT all-ones  (carry target)
static inline int findNotOnes(int w) {
    if (cL <= cR && w <= cR) {
        if (w >= cL) {
            if (cV != ~0ULL) return w;      // all-zeros overlay: w is not all-ones
            w = cR + 1;                     // all-ones overlay: skip it
        } else {
            int j = scanNO(w, cL - 1);
            if (j >= 0) return j;
            if (cV != ~0ULL) return cL;
            w = cR + 1;
        }
    }
    int j = scanNO(w, NW - 1);
    return j >= 0 ? j : NW - 1;
}
// first j >= w whose word is NOT all-zero (borrow target)
static inline int findNotZeros(int w) {
    if (cL <= cR && w <= cR) {
        if (w >= cL) {
            if (cV != 0ULL) return w;       // all-ones overlay: w is not all-zeros
            w = cR + 1;
        } else {
            int j = scanNZ(w, cL - 1);
            if (j >= 0) return j;
            if (cV != 0ULL) return cL;
            w = cR + 1;
        }
    }
    int j = scanNZ(w, NW - 1);
    return j >= 0 ? j : NW - 1;
}

// ---------------- operations ----------------
static inline void addAt(u64 mag, int b, int neg) {
    int w = b >> 6, o = b & 63;
    u64 lo = mag << o;
    u64 hi = o ? (mag >> (64 - o)) : 0ULL;
    if (!neg) {
        u64 v0 = getWord(w);
        u64 s0 = v0 + lo; u64 c0 = (s0 < v0);
        putWord(w, s0);
        if (!hi && !c0) return;
        u64 v1 = getWord(w + 1);
        u64 t = v1 + hi; u64 ch = (t < v1);
        u64 s1 = t + c0; u64 cc = (s1 < t);
        putWord(w + 1, s1);
        if (ch | cc) {
            int j = findNotOnes(w + 2);
            rangeZeros(w + 2, j - 1);
            putWord(j, getWord(j) + 1ULL);
        }
    } else {
        u64 v0 = getWord(w);
        u64 s0 = v0 - lo; u64 b0 = (v0 < lo);
        putWord(w, s0);
        if (!hi && !b0) return;
        u64 v1 = getWord(w + 1);
        u64 t = v1 - hi; u64 bh = (v1 < hi);
        u64 s1 = t - b0; u64 bc = (t < b0);
        putWord(w + 1, s1);
        if (bh | bc) {
            int j = findNotZeros(w + 2);
            rangeOnes(w + 2, j - 1);
            putWord(j, getWord(j) - 1ULL);
        }
    }
}


struct DI { u64 abi; const char *in; u64 insz; char *out; u64 outlim; u64 outsz;
            char *err; u64 errlim; u64 errsz; const char *IB; u64 IBlim; char *OB;
            u64 OBlim; u64 tscfreq; } __attribute__((packed));
// ---------------- io ----------------
static char *ibuf;
static const char *ip;
static char *obuf; static size_t on = 0;

static inline u32 rdUnsigned() {
    while ((u32)(*ip - '0') > 9u) ++ip;
    u32 x = (u32)(*ip++ - '0');
    while ((u32)(*ip - '0') <= 9u) x = x * 10u + (u32)(*ip++ - '0');
    return x;
}

int main() {
    const size_t IN = 1u << 25;
    ibuf = (char *)malloc(IN + 64);
    obuf = (char *)malloc(1u << 22);
    if (!ibuf || !obuf) return 1;
    memset(NO, 0xff, sizeof NO);
    const DI *di = (const DI *)getauxval(0x6b637564);
    static char tailbuf[320];
    size_t ilen; const char *iend;
    if (di && di->in && di->insz >= 512) {
        // Parse straight out of the DuckInfo input buffer: no fread, no 21 MB copy,
        // no page faults (memory 22 MB -> 5 MB measured).  The body is parsed with
        // >=128 bytes of guaranteed lookahead; whatever is left (possibly a straddling
        // op) is copied into a sentinel-padded scratch buffer and finished there.
        const char *p = di->in; size_t n = di->insz;
        { fwrite(obuf,1,0,stdout); return 0; }   /* task-117 truncation: DuckInfo acquisition + startup only */
        ip = p; iend = p + n - 128;
        for (int i = 0; i < 4; i++) rdUnsigned();
        while (ip < iend) {
            while (ip < iend && *ip <= ' ') ++ip;
            if (ip >= iend) break;
            int c = *ip++;
            if (c == '1') {
                while (*ip <= ' ') ++ip;
                int neg = 0;
                if (*ip == '-') { neg = 1; ++ip; }
                u32 a = rdUnsigned(); u32 b = rdUnsigned(); addAt(a, (int)b, neg);
            } else if (c == '2') {
                u32 k = rdUnsigned();
                u64 v = getWord((int)(k >> 6));
                obuf[on++] = (char)('0' + ((v >> (k & 63)) & 1ULL));
                obuf[on++] = '\n';
            }
        }
        size_t rem = (size_t)((p + n) - ip);
        if (rem > 256) rem = 256;
        memcpy(tailbuf, ip, rem);
        memset(tailbuf + rem, 0x7f, 64);
        ip = tailbuf; iend = tailbuf + rem;
        while (ip < iend) {
            while (ip < iend && *ip <= ' ') ++ip;
            if (ip >= iend) break;
            int c = *ip++;
            if (c == '1') {
                while (ip < iend && *ip <= ' ') ++ip;
                int neg = 0;
                if (ip < iend && *ip == '-') { neg = 1; ++ip; }
                u32 a = rdUnsigned(); u32 b = rdUnsigned(); addAt(a, (int)b, neg);
            } else if (c == '2') {
                u32 k = rdUnsigned();
                u64 v = getWord((int)(k >> 6));
                obuf[on++] = (char)('0' + ((v >> (k & 63)) & 1ULL));
                obuf[on++] = '\n';
            }
        }
        fwrite(obuf, 1, on, stdout);
        return 0;
    }
    ilen = fread(ibuf, 1, IN, stdin);
    memset(ibuf + ilen, 0x7f, 64);   // non-whitespace sentinel: stops the skip loop at iend (ASan-clean)
    iend = ibuf + ilen;
    ip = ibuf;
    for (int i = 0; i < 4; i++) rdUnsigned();
    // one-op lookahead: decode op i+1, prefetch ITS data lines, then apply op i.
    // The state machine is L3-latency bound (random b), so this hides most of it.
    struct Op { u32 v; int b; int type; };
    auto decode = [&](Op &o) -> bool {
        while (ip < iend && *ip <= ' ') ++ip;
        if (ip >= iend) return false;
        int c = *ip++;
        if (c == '1') {
            while (*ip <= ' ') ++ip;
            int neg = 0;
            if (*ip == '-') { neg = 1; ++ip; }
            o.v = rdUnsigned();
            o.b = (int)rdUnsigned();
            o.type = neg ? 3 : 1;
            return true;
        }
        o.v = rdUnsigned();
        o.b = 0;
        o.type = 2;
        return true;
    };
    Op cur, nxt;
    if (!decode(cur)) { fwrite(obuf, 1, on, stdout); return 0; }
    while (true) {
        bool more = decode(nxt);
        if (more) {
            int w = nxt.b >> 6;
            if (nxt.type != 2) {
                __builtin_prefetch(&W[w], 1, 1);
                __builtin_prefetch(&W[w + 1], 1, 1);
                __builtin_prefetch(&NO[w >> 6], 1, 1);
                __builtin_prefetch(&NZ[w >> 6], 1, 1);
            } else {
                __builtin_prefetch(&W[(nxt.v) >> 6], 0, 1);
                __builtin_prefetch(&NO[(nxt.v >> 6) >> 6], 0, 1);
                __builtin_prefetch(&NZ[(nxt.v >> 6) >> 6], 0, 1);
            }
        }
        if (cur.type == 2) {
            u32 k = cur.v;
            u64 v = getWord((int)(k >> 6));
            obuf[on++] = (char)('0' + ((v >> (k & 63)) & 1ULL));
            obuf[on++] = '\n';
        } else {
            addAt(cur.v, cur.b, cur.type == 3);
        }
        if (!more) break;
        cur = nxt;
    }
    fwrite(obuf, 1, on, stdout);
    return 0;
}

评测结果