代码

#include <stdint.h>
#include <sys/auxv.h>
#include <unistd.h>
#include <immintrin.h>
#pragma GCC target("avx2,bmi,bmi2")

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

typedef unsigned __int128 u128;
#define FULL ((u128)-1)
#define NB 234496
#define N1 3664
#define N2 58

static u128 blk[NB];
static uint64_t fm1[N1], nm1[N1];
static uint64_t fm2[N2], nm2[N2];
static uint64_t fm3, nm3;

static uint64_t O;
static char *out;

/* ---------- tokenizer ---------- */
#define IBUF_SIZE (32*1024*1024)
#define MAXTOK (3000008)
static char ibuf[IBUF_SIZE + 64];
static uint32_t val_arr[MAXTOK];

static const int8_t sh[9][16] __attribute__((aligned(16))) = {
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {-128,-128,-128,-128,-128,-128,-128,0,  -128,-128,-128,-128,-128,-128,-128,-128},
    {-128,-128,-128,-128,-128,-128,0,1,     -128,-128,-128,-128,-128,-128,-128,-128},
    {-128,-128,-128,-128,-128,0,1,2,        -128,-128,-128,-128,-128,-128,-128,-128},
    {-128,-128,-128,-128,0,1,2,3,           -128,-128,-128,-128,-128,-128,-128,-128},
    {-128,-128,-128,0,1,2,3,4,              -128,-128,-128,-128,-128,-128,-128,-128},
    {-128,-128,0,1,2,3,4,5,                 -128,-128,-128,-128,-128,-128,-128,-128},
    {-128,0,1,2,3,4,5,6,                    -128,-128,-128,-128,-128,-128,-128,-128},
    {0,1,2,3,4,5,6,7,                        -128,-128,-128,-128,-128,-128,-128,-128},
};

static inline uint32_t conv8(const char *p, int L){
    __m128i v = _mm_loadu_si128((const __m128i*)p);
    __m128i d = _mm_sub_epi8(v, _mm_set1_epi8('0'));
    __m128i a = _mm_shuffle_epi8(d, _mm_load_si128((const __m128i*)sh[L]));
    __m128i m = _mm_maddubs_epi16(a, _mm_setr_epi8(10,1,10,1,10,1,10,1,10,1,10,1,10,1,10,1));
    __m128i m2 = _mm_madd_epi16(m, _mm_setr_epi16(100,1,100,1,100,1,100,1));
    __m128i m3 = _mm_mullo_epi32(m2, _mm_setr_epi32(10000,1,10000,1));
    __m128i h = _mm_hadd_epi32(m3, m3);
    return (uint32_t)_mm_cvtsi128_si32(h);
}

static inline void emit(const char *p, uint32_t *cnt, uint32_t start, int L){
    uint32_t v;
    if (L > 8){
        int h = p[start] - '0';
        const char *lo = p + start + 1;
        if (L == 10){ h = h*10 + (p[start+1]-'0'); lo = p + start + 2; }
        v = (uint32_t)h * 100000000u + conv8(lo, 8);
    } else if (L == 1){
        v = (uint32_t)(p[start] - '0');
    } else {
        v = conv8(p + start, L);
    }
    if (start && p[start - 1] == '-') v = (uint32_t)(-(int32_t)v);
    val_arr[(*cnt)++] = v;
}

/* fused: SIMD scan + convert in one pass */
static inline uint32_t parse_all(const char *p, uint64_t size){
    uint32_t cnt = 0;
    int carry = 0;
    uint32_t run_start = 0;
    const __m256i zl = _mm256_set1_epi8('0' - 1);
    uint64_t pos = 0;
    for (; pos < size; pos += 32){
        __m256i v = _mm256_loadu_si256((const __m256i*)(p + pos));
        __m256i d = _mm256_cmpgt_epi8(v, zl);
        uint32_t dm = (uint32_t)_mm256_movemask_epi8(d);
        if (pos + 32 > size) dm &= (1u << (size - pos)) - 1;
        if (carry){
            int f0 = __builtin_ctz(~dm);
            emit(p, &cnt, run_start, (int)((uint32_t)(pos - run_start) + (uint32_t)f0));
            carry = 0;
            dm &= ~((1u << (f0 + 1)) - 1);
        }
        if (dm & 0x80000000u){
            int s_last = 32 - __builtin_clz(~dm);
            run_start = (uint32_t)pos + (uint32_t)s_last;
            carry = 1;
            dm &= (1u << s_last) - 1;
        }
        uint32_t starts = dm & ~(dm << 1);
        uint32_t ends   = dm & ~(dm >> 1);
        uint32_t st = starts, en = ends;
        while (st){
            int s = __builtin_ctz(st);
            int e = __builtin_ctz(en);
            emit(p, &cnt, (uint32_t)pos + (uint32_t)s, e - s + 1);
            st &= st - 1;
            en &= en - 1;
        }
    }
    if (carry){
        emit(p, &cnt, run_start, (int)(size - run_start));
    }
    return cnt;
}

/* ---------- core (verbatim from solution_v6.c) ---------- */

static inline int ctz(uint64_t x){ return __builtin_ctzll(x); }

static inline int point_add(int pos, u128 v){
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    int ovf;
    {
        uint64_t b = 1ull << l2;
        if (fm3 & b){ fm2[l2] = ~0ull; nm2[l2] = ~0ull; }
        else if (!(nm3 & b)){ fm2[l2] = 0; nm2[l2] = 0; }
    }
    {
        uint64_t b = 1ull << (l1 & 63);
        if (fm2[l2] & b){ fm1[l1] = ~0ull; nm1[l1] = ~0ull; }
        else if (!(nm2[l2] & b)){ fm1[l1] = 0; nm1[l1] = 0; }
    }
    {
        uint64_t b = 1ull << (pos & 63);
        u128 old;
        if (fm1[l1] & b) old = FULL;
        else if (!(nm1[l1] & b)) old = 0;
        else old = blk[pos];
        u128 nv = old + v;
        blk[pos] = nv;
        ovf = nv < old;
        if (nv == FULL) fm1[l1] |= b; else fm1[l1] &= ~b;
        if (nv != 0) nm1[l1] |= b; else nm1[l1] &= ~b;
    }
    {
        uint64_t b = 1ull << (l1 & 63);
        if (fm1[l1] == ~0ull) fm2[l2] |= b; else fm2[l2] &= ~b;
        if (nm1[l1] != 0) nm2[l2] |= b; else nm2[l2] &= ~b;
    }
    {
        uint64_t b = 1ull << l2;
        if (fm2[l2] == ~0ull) fm3 |= b; else fm3 &= ~b;
        if (nm2[l2] != 0) nm3 |= b; else nm3 &= ~b;
    }
    return ovf;
}

static inline int point_sub(int pos, u128 v){
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    int ovf;
    {
        uint64_t b = 1ull << l2;
        if (fm3 & b){ fm2[l2] = ~0ull; nm2[l2] = ~0ull; }
        else if (!(nm3 & b)){ fm2[l2] = 0; nm2[l2] = 0; }
    }
    {
        uint64_t b = 1ull << (l1 & 63);
        if (fm2[l2] & b){ fm1[l1] = ~0ull; nm1[l1] = ~0ull; }
        else if (!(nm2[l2] & b)){ fm1[l1] = 0; nm1[l1] = 0; }
    }
    {
        uint64_t b = 1ull << (pos & 63);
        u128 old;
        if (fm1[l1] & b) old = FULL;
        else if (!(nm1[l1] & b)) old = 0;
        else old = blk[pos];
        u128 nv = old - v;
        blk[pos] = nv;
        ovf = nv > old;
        if (nv == FULL) fm1[l1] |= b; else fm1[l1] &= ~b;
        if (nv != 0) nm1[l1] |= b; else nm1[l1] &= ~b;
    }
    {
        uint64_t b = 1ull << (l1 & 63);
        if (fm1[l1] == ~0ull) fm2[l2] |= b; else fm2[l2] &= ~b;
        if (nm1[l1] != 0) nm2[l2] |= b; else nm2[l2] &= ~b;
    }
    {
        uint64_t b = 1ull << l2;
        if (fm2[l2] == ~0ull) fm3 |= b; else fm3 &= ~b;
        if (nm2[l2] != 0) nm3 |= b; else nm3 &= ~b;
    }
    return ovf;
}

static inline void zero_full_l2(int l2, int off2){
    int pos = (l2 << 12) + off2;
    int l1 = pos >> 6, off = pos & 63;
    int l1in = l1 & 63;
    fm1[l1] = (off == 0) ? 0 : ((1ull << off) - 1);
    nm1[l1] = fm1[l1];
    fm2[l2] = (1ull << l1in) - 1;
    nm2[l2] = (off == 0) ? fm2[l2] : (fm2[l2] | (1ull << l1in));
    uint64_t b3 = 1ull << l2;
    fm3 &= ~b3;
    nm3 |= b3;
}

static inline void zero_full_l1(int l1, int off){
    fm1[l1] = (1ull << off) - 1;
    nm1[l1] = (1ull << off) - 1;
    int l2 = l1 >> 6;
    uint64_t b2 = 1ull << (l1 & 63);
    fm2[l2] &= ~b2;
    nm2[l2] |= b2;
}

static inline void set_full_l2(int l2, int off2){
    int pos = (l2 << 12) + off2;
    int l1 = pos >> 6, off = pos & 63;
    int l1in = l1 & 63;
    fm1[l1] = ~0ull << off;
    nm1[l1] = fm1[l1];
    fm2[l2] = ~0ull << l1in;
    nm2[l2] = fm2[l2];
    uint64_t b3 = 1ull << l2;
    if (fm2[l2] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
    nm3 |= b3;
}

static inline void set_full_l1(int l1, int off){
    fm1[l1] = ~0ull << off;
    nm1[l1] = ~0ull << off;
    int l2 = l1 >> 6;
    uint64_t b2 = 1ull << (l1 & 63);
    if (fm1[l1] == ~0ull) fm2[l2] |= b2; else fm2[l2] &= ~b2;
    nm2[l2] |= b2;
}

static inline void carry_add(int p){
    int l2 = p >> 12, l1 = p >> 6, off = p & 63;
    int off2 = p & 4095;
    uint64_t m3 = ~fm3 >> l2;
    int l2pos = (off2 == 0) ? l2 : l2 + 1;
    if (off2 > 0 && (fm3 & (1ull << l2))){
        zero_full_l2(l2, off2);
    }
    while (m3){
        int l2n = l2 + ctz(m3);
        uint64_t b3 = 1ull << l2n;
        if (l2n > l2pos){
            uint64_t zm = ((1ull << (l2n - l2pos)) - 1) << l2pos;
            fm3 &= ~zm; nm3 &= ~zm;
        }
        l2pos = l2n + 1;
        if (!(nm3 & b3)){
            if (l2n > l2){
                int l1n = l2n << 6;
                blk[l2n << 12] = 1;
                fm1[l1n] = 0; nm1[l1n] = 1ull;
                fm2[l2n] = 0; nm2[l2n] = 1ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            } else {
                uint64_t b1 = 1ull << off;
                blk[p] = 1;
                fm1[l1] = 0; nm1[l1] = b1;
                uint64_t b2 = 1ull << (l1 & 63);
                fm2[l2] = 0; nm2[l2] = b2;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
        }
        int c2 = (l2n == l2) ? (l1 & 63) : 0;
        uint64_t m2 = ~fm2[l2n] >> c2;
        int c2pos = c2;
        if (l2n == l2 && off > 0 && (fm2[l2n] & (1ull << c2))){
            zero_full_l1(l1, off);
            c2pos = c2 + 1;
        }
        while (m2){
            int c2r = c2 + ctz(m2);
            uint64_t b2 = 1ull << c2r;
            int l1n = (l2n << 6) + c2r;
            if (c2r > c2pos){
                uint64_t zm = ((1ull << (c2r - c2pos)) - 1) << c2pos;
                fm2[l2n] &= ~zm; nm2[l2n] &= ~zm;
            }
            c2pos = c2r + 1;
            if (!(nm2[l2n] & b2)){
                if (l1n > l1){
                    blk[l1n << 6] = 1;
                    fm1[l1n] = 0; nm1[l1n] = 1ull;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                } else {
                    uint64_t b1 = 1ull << off;
                    blk[p] = 1;
                    fm1[l1] = 0; nm1[l1] = b1;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                }
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            int c1 = (l1n == l1) ? off : 0;
            uint64_t m1 = ~fm1[l1n] >> c1;
            if (m1){
                int c1r = c1 + ctz(m1);
                int j = (l1n << 6) + c1r;
                uint64_t b1 = 1ull << c1r;
                if (c1r > c1){
                    uint64_t zm = ((1ull << (c1r - c1)) - 1) << c1;
                    fm1[l1n] &= ~zm; nm1[l1n] &= ~zm;
                }
                if (nm1[l1n] & b1){
                    u128 nv = blk[j] + 1;
                    blk[j] = nv;
                    if (nv == FULL) fm1[l1n] |= b1; else fm1[l1n] &= ~b1;
                    nm1[l1n] |= b1;
                } else {
                    blk[j] = 1;
                    fm1[l1n] &= ~b1; nm1[l1n] |= b1;
                }
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            {
                uint64_t zm = ~0ull << c1;
                fm1[l1n] &= ~zm; nm1[l1n] &= ~zm;
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
            }
            m2 &= m2 - 1;
        }
        if (c2pos < 64){
            uint64_t zm = ~0ull << c2pos;
            fm2[l2n] &= ~zm; nm2[l2n] &= ~zm;
        }
        if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
        if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
        m3 &= m3 - 1;
    }
}

static inline void borrow_sub(int p){
    int l2 = p >> 12, l1 = p >> 6, off = p & 63;
    int off2 = p & 4095;
    uint64_t m3 = nm3 >> l2;
    int l2pos = (off2 == 0) ? l2 : l2 + 1;
    if (off2 > 0 && !(nm3 & (1ull << l2))){
        set_full_l2(l2, off2);
    }
    while (m3){
        int l2n = l2 + ctz(m3);
        uint64_t b3 = 1ull << l2n;
        if (l2n > l2pos){
            uint64_t zm = ((1ull << (l2n - l2pos)) - 1) << l2pos;
            fm3 |= zm; nm3 |= zm;
        }
        l2pos = l2n + 1;
        if (fm3 & b3){
            if (l2n > l2){
                int l1n = l2n << 6;
                blk[l2n << 12] = FULL - 1;
                fm1[l1n] = ~0ull ^ 1ull; nm1[l1n] = ~0ull;
                fm2[l2n] = ~0ull ^ 1ull; nm2[l2n] = ~0ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            } else {
                uint64_t b1 = 1ull << off;
                blk[p] = FULL - 1;
                fm1[l1] = ~0ull ^ b1; nm1[l1] = ~0ull;
                uint64_t b2 = 1ull << (l1 & 63);
                fm2[l2] = ~0ull ^ b2; nm2[l2] = ~0ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
        }
        int c2 = (l2n == l2) ? (l1 & 63) : 0;
        uint64_t m2 = nm2[l2n] >> c2;
        int c2pos = c2;
        if (l2n == l2 && off > 0 && !(nm2[l2n] & (1ull << c2))){
            set_full_l1(l1, off);
            c2pos = c2 + 1;
        }
        while (m2){
            int c2r = c2 + ctz(m2);
            uint64_t b2 = 1ull << c2r;
            int l1n = (l2n << 6) + c2r;
            if (c2r > c2pos){
                uint64_t zm = ((1ull << (c2r - c2pos)) - 1) << c2pos;
                fm2[l2n] |= zm; nm2[l2n] |= zm;
            }
            c2pos = c2r + 1;
            if (fm2[l2n] & b2){
                if (l1n > l1){
                    blk[l1n << 6] = FULL - 1;
                    fm1[l1n] = ~0ull ^ 1ull; nm1[l1n] = ~0ull;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                } else {
                    uint64_t b1 = 1ull << off;
                    blk[p] = FULL - 1;
                    fm1[l1] = ~0ull ^ b1; nm1[l1] = ~0ull;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                }
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            int c1 = (l1n == l1) ? off : 0;
            uint64_t m1 = nm1[l1n] >> c1;
            if (m1){
                int c1r = c1 + ctz(m1);
                int j = (l1n << 6) + c1r;
                uint64_t b1 = 1ull << c1r;
                if (c1r > c1){
                    uint64_t zm = ((1ull << (c1r - c1)) - 1) << c1;
                    fm1[l1n] |= zm; nm1[l1n] |= zm;
                }
                if (fm1[l1n] & b1){
                    blk[j] = FULL - 1;
                    fm1[l1n] &= ~b1; nm1[l1n] |= b1;
                } else {
                    u128 nv = blk[j] - 1;
                    blk[j] = nv;
                    if (nv == 0) nm1[l1n] &= ~b1; else nm1[l1n] |= b1;
                }
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            {
                uint64_t zm = ~0ull << c1;
                fm1[l1n] |= zm; nm1[l1n] |= zm;
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
            }
            m2 &= m2 - 1;
        }
        if (c2pos < 64){
            uint64_t zm = ~0ull << c2pos;
            fm2[l2n] |= zm; nm2[l2n] |= zm;
        }
        if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
        if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
        m3 &= m3 - 1;
    }
}

static inline void add_val(int q, int r, uint64_t av){
    u128 lo = (u128)av << r;
    uint64_t hi = 0;
    if (r >= 99) hi = av >> (128 - r);
    if (point_add(q, lo)) carry_add(q + 1);
    if (hi && point_add(q + 1, (u128)hi)) carry_add(q + 2);
}
static inline void sub_val(int q, int r, uint64_t av){
    u128 lo = (u128)av << r;
    uint64_t hi = 0;
    if (r >= 99) hi = av >> (128 - r);
    if (point_sub(q, lo)) borrow_sub(q + 1);
    if (hi && point_sub(q + 1, (u128)hi)) borrow_sub(q + 2);
}

__attribute__((noreturn)) static void done(uint64_t olen, struct DuckInfo *di, int use_di){
    if (use_di) di->stdout_size = olen;
    else (void)!write(1, out, olen);
    asm volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax","rdi","memory");
    __builtin_unreachable();
}

int main(){
    struct DuckInfo *di = (struct DuckInfo*)getauxval(0x6b637564);
    uint64_t size;
    const char *P;
    int use_di = 0;
    if (di && di->abi_version >= 1 && di->stdin_ptr && di->stdout_ptr){
        size = di->stdin_size;
        P = di->stdin_ptr;
        out = di->stdout_ptr;
        use_di = 1;
    } else {
        long n2 = 0, t;
        while (n2 < IBUF_SIZE && (t = read(0, ibuf + n2, IBUF_SIZE - n2)) > 0) n2 += t;
        size = (uint64_t)n2;
        for (int j = 0; j < 64; j++) ibuf[n2 + j] = ' ';
        P = ibuf;
        static char obuf[1<<22];
        out = obuf;
    }

    uint32_t cnt = parse_all(P, size);

    int n = (int32_t)val_arr[0];
    uint32_t idx = 4;
    for (int i = 0; i < n; i++){
        int op = (int32_t)val_arr[idx++];
        if (op == 1){
            int a = (int32_t)val_arr[idx++];
            int b = (int32_t)val_arr[idx++];
            int q = b >> 7;
            int r = b & 127;
            if (a < 0) sub_val(q, r, (uint64_t)(-(int64_t)a));
            else if (a) add_val(q, r, (uint64_t)a);
        } else {
            int k = (int32_t)val_arr[idx++];
            int q = k >> 7;
            int r = k & 127;
            uint64_t v;
            {
                int l2 = q >> 12, l1 = q >> 6;
                uint64_t b3 = 1ull << l2;
                if (fm3 & b3) v = 1;
                else if (!(nm3 & b3)) v = 0;
                else {
                    uint64_t b2 = 1ull << (l1 & 63);
                    if (fm2[l2] & b2) v = 1;
                    else if (!(nm2[l2] & b2)) v = 0;
                    else {
                        uint64_t b1 = 1ull << (q & 63);
                        if (fm1[l1] & b1) v = 1;
                        else if (!(nm1[l1] & b1)) v = 0;
                        else v = (uint64_t)((blk[q] >> r) & 1);
                    }
                }
            }
            out[O++] = (char)('0' + (v & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, use_di);
}

评测结果