代码

#include <stdint.h>
#include <sys/auxv.h>
#include <unistd.h>

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));

#define FULL 0xFFFFFFFFu
#define N (1u<<20)          /* digits (base 2^32) */
#define B 512               /* block size */
#define NB (N/B)            /* 2048 blocks */

static uint32_t d[N];
static uint8_t bt[NB];      /* 0=all-zero(lazy), 1=all-full(lazy), 2=mixed */

static const char *P;
static uint64_t O;

static inline void materialize(int b){
    if (bt[b] == 0){
        uint32_t *p = d + (b << 9);
        for (int i = 0; i < B; i++) p[i] = 0;
        bt[b] = 2;
    } else if (bt[b] == 1){
        uint32_t *p = d + (b << 9);
        for (int i = 0; i < B; i++) p[i] = FULL;
        bt[b] = 2;
    }
}

/* add v to digit q, return carry */
static inline int point_add(int q, uint32_t v){
    int b = q >> 9;
    materialize(b);
    uint32_t old = d[q];
    uint64_t s = (uint64_t)old + v;
    d[q] = (uint32_t)s;
    return (int)(s >> 32);
}

static inline int point_sub(int q, uint32_t v){
    int b = q >> 9;
    materialize(b);
    uint32_t old = d[q];
    uint32_t nv = old - v;
    d[q] = nv;
    return (int)(old < v);
}

/* find first non-full digit >= p, zeroing the full digits in [p, j-1]; return j */
static inline int carry_find(int p){
    int j = p;
    for (;;){
        int b = j >> 9;
        uint8_t tag = bt[b];
        if (tag == 1){ bt[b] = 0; j = (b + 1) << 9; continue; }
        if (tag == 0){ return j; }
        /* mixed: scan */
        int start = j;
        int end = (b + 1) << 9;
        while (j < end && d[j] == FULL){ d[j] = 0; j++; }
        if (j < end) return j;
        /* zeroed [start, end); whole block only if start was aligned */
        bt[b] = (start == (b << 9)) ? 0 : 2;
    }
}

/* find first non-zero digit >= p, filling the zero digits in [p, j-1] with FULL; return j */
static inline int borrow_find(int p){
    int j = p;
    for (;;){
        int b = j >> 9;
        uint8_t tag = bt[b];
        if (tag == 0){ bt[b] = 1; j = (b + 1) << 9; continue; }
        if (tag == 1){ return j; }
        /* mixed: scan */
        int start = j;
        int end = (b + 1) << 9;
        while (j < end && d[j] == 0){ d[j] = FULL; j++; }
        if (j < end) return j;
        bt[b] = (start == (b << 9)) ? 1 : 2;
    }
}

static inline void carry_add(int p){
    int j = carry_find(p);
    point_add(j, 1u);
}
static inline void borrow_sub(int p){
    int j = borrow_find(p);
    point_sub(j, 1u);
}

static inline void add_val(int q, int r, uint32_t av){
    uint64_t v = (uint64_t)av << r;
    uint32_t lo = (uint32_t)v, hi = (uint32_t)(v >> 32);
    uint32_t c = point_add(q, lo);
    if (point_add(q + 1, hi + c)) carry_add(q + 2);
}
static inline void sub_val(int q, int r, uint32_t av){
    uint64_t v = (uint64_t)av << r;
    uint32_t lo = (uint32_t)v, hi = (uint32_t)(v >> 32);
    uint32_t c = point_sub(q, lo);
    if (point_sub(q + 1, hi + c)) borrow_sub(q + 2);
}

static inline int rd(){
    while (*P <= ' ') P++;
    int v = 0;
    while (*P > ' ') v = v*10 + (*P - '0'), P++;
    return v;
}
static inline int rds(){
    while (*P <= ' ') P++;
    int neg = 0;
    if (*P == '-'){ neg = 1; P++; }
    int v = 0;
    while (*P > ' ') v = v*10 + (*P - '0'), P++;
    return neg ? -v : v;
}

__attribute__((noreturn)) static void done(uint64_t olen, struct DuckInfo *di, char *out, 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);
    static char lbuf[1<<24];
    static char obuf[1<<22];
    char *out;
    int use_di = 0;
    if (di && di->abi_version >= 1 && di->stdin_ptr && di->stdout_ptr){
        P = di->stdin_ptr;
        out = di->stdout_ptr;
        use_di = 1;
    } else {
        long n2 = 0, t;
        while (n2 < (long)sizeof(lbuf) && (t = read(0, lbuf + n2, sizeof(lbuf) - n2)) > 0) n2 += t;
        lbuf[n2] = 0;
        P = lbuf;
        out = obuf;
    }

    int n = rd();
    rd(); rd(); rd();

    for (int i = 0; i < n; i++){
        int op = rd();
        if (op == 1){
            int a = rds();
            int b = rd();
            int q = b >> 5;
            int r = b & 31;
            if (a > 0) add_val(q, r, (uint32_t)a);
            else if (a < 0) sub_val(q, r, (uint32_t)(-(int64_t)a));
        } else {
            int k = rd();
            int q = k >> 5;
            int r = k & 31;
            uint32_t v;
            int b = q >> 9;
            if (bt[b] == 0) v = 0;
            else if (bt[b] == 1) v = 1;
            else v = (d[q] >> r) & 1;
            out[O++] = (char)('0' + (v & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果