#include #include #include #include static bool debug; static long long delna_vsota (long * vreča, long bis, int exp) { long long r = 0; long last = 0; for (long i = 0; i <= exp; i++) { if (last + (1 << (exp-i)) <= bis) { long idx = (1 << i)-1 + ((last) >> (exp-i)); r += vreča[idx]; if (debug) fprintf(stderr, "i=%ld\tlast=%ld\tidx=%ld\tr=%lld\n", i, last, idx, r); last += (1 << (exp-i)); } } if (debug) fprintf(stderr, "delna vsota prvih %ld je %lld\n", bis, r); return r; } static void print_vreča (long * vreča, int exp) { for (int i = 0; i <= exp; i++) { for (int j = 0; j < (1 << i); j++) fprintf(stderr, "% *ld", 2*(1 << (exp-i)), vreča[(1 << i)-1+j]); fprintf(stderr, "\n"); } } int main (void) { long n; debug = getenv("DEBUG"); int exp = atoi(getenv("EXP") ? getenv("EXP") : "20"); // [0, 2**exp] so možna števila v vreči scanf("%ld", &n); long * vreča = (long *) calloc(1L << (exp+1), sizeof *vreča); long long r = 0; for (long i = 0; i < n; i++) { if (debug) print_vreča(vreča, exp); long s, x; scanf("%ld %ld", &s, &x); if (s <= 0) { // dodamo x v vrečo za s < 0, odstranimo za s == 0 if (debug) fprintf(stderr, "%s %ld\n", s ? "vstavljam" : "odstranjujem", x); if (!s && !vreča[(1 << exp)-1+x]) { if (debug) fprintf(stderr, "preskakujem odstranjevanje, saj števila ni v vreči\n"); continue; } for (long i = 0; i <= exp; i++) vreča[(1 << i)-1+(x >> (exp-i))] += s ? 1 : -1; } else { // poizvedba na intervalu long a = MIN(s, x); long b = MAX(s, x); long long odgovor = delna_vsota(vreča, b+1, exp)-delna_vsota(vreča, a, exp); if (debug) fprintf(stderr, "odgovor na poizvedbo [%ld, %ld]: %lld\n", a, b, odgovor); r += odgovor; } } printf("%lld\n", r); }