Submission #12902

#TimeUsernameProblemLanguageResultExecution timeMemory
12902tncks0121즐거운 사진 수집 (JOI13_collecting)C++14
0 / 100
16 ms102028 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <utility> #include <bitset> #include <limits.h> #include <iostream> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; const int K_ = 20; const int N_ = 1<<20; int N, Q, K; struct node { int s; ll c, a; node (int s = 0, ll c = 1, ll a = 0): s(s), c(c), a(a) { } }; node tree0[N_+N_+5], tree1[N_+N_+5]; ll full1[K_]; bool cur[2][N_]; ll coef0[K_]; node merge0 (node x, node y, int h) { node ret; ret.s = x.s + y.s; ret.c = (ret.s == 0 || ret.s == (1<<(K-h))) ? 1 : (1 + (x.c + y.c) * 2); ret.a = (ret.c == 1) ? 0 : ((1 << h) + (x.a + y.a)); return ret; } void upd0 (int nd, int h, int x, int v) { if(nd >= N) { tree0[nd] = node(v, 1, 0); return; } int d = ((x >> (K - h - 1)) & 1); if(tree0[nd].c == 1) { coef0[h]--; coef0[h+1] += 2; } upd0(nd+nd+d, h + 1, x, v); tree0[nd] = merge0(tree0[nd+nd], tree0[nd+nd+1], h); if(tree0[nd].c == 1) coef0[h]++; } void upd1 (int x, int v) { x += N; tree1[x] = node(v, 1, 0); for(int h = K-1, u = x; u >>= 1; h--) { full1[h] -= tree1[u].c; tree1[u] = merge0(tree1[u+u], tree1[u+u+1], h); full1[h] += tree1[u].c; } } int main() { scanf("%d%d", &K, &Q); N = 1<<K; for(int h = 0; h <= K; h++) full1[h] = 1 << h; for(int h = 0, i = 1; i < N+N; i++) { tree0[i] = tree1[i] = node(0, 1, 0); if(i == (2<<h) - 1) ++h; } coef0[0] = 1; while(Q--) { int t, x; scanf("%d%d", &t, &x); --x; cur[t][x] = !cur[t][x]; if(t == 0) { upd0(1, 0, x, cur[t][x]); }else { upd1(x, cur[t][x]); } ll ans = tree0[1].a; for(int i = 0; i <= K; i++) ans += coef0[i] * full1[i]; printf("%lld\n", ans); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...