Submission #43192

#TimeUsernameProblemLanguageResultExecution timeMemory
43192baactree즐거운 사진 수집 (JOI13_collecting)C++14
0 / 100
5046 ms44268 KiB
#include <bits/stdc++.h> using namespace std; int n, q; int r[21][1 << 20], c[21][1 << 20]; int rs[1 << 21], cs[1 << 21]; int ro[1 << 20], co[1 << 20]; void update(int idx, int val, int *tree) { idx += 2; while (idx < 1 << 21) { tree[idx] += val; idx += idx&(-idx); } } int query(int idx, int *tree) { int ret = 0; idx += 2; while (idx) { ret += tree[idx]; idx -= idx&(-idx); } return ret; } int main() { scanf("%d%d", &n, &q); long long cnt = 0; for (int i = 1; i <= n; i++) r[i][0] = c[i][0] = 1 << (n - i); while (q--) { int a, b; scanf("%d%d", &a, &b); b--; if (a) { //col for (int i = 1; i <= n; i++) { int d = 1 << i; int idx = b / d; int le = idx*d; int ri = (idx + 1)*d - 1; int pre = query(ri, cs) - query(le - 1, cs); c[i][pre]--; update(b, co[b] ? -1 : 1, cs); co[b] ^= 1; int now = (query(ri, cs) - query(le - 1, cs))%(1<<i); c[i][now]++; int k = 0; if (pre == 0)k = 1; else if (now == 0)k = -1; cnt += r[i][0] * k; update(b, co[b] ? -1 : 1, cs); co[b] ^= 1; } update(b, co[b] ? -1 : 1, cs); co[b] ^= 1; } else { //row for (int i = 1; i <= n; i++) { int d = 1 << i; int idx = b / d; int le = idx*d; int ri = (idx + 1)*d - 1; int pre = query(ri, rs) - query(le - 1, rs); r[i][pre]--; update(b, ro[b] ? -1 : 1, rs); ro[b] ^= 1; int now = (query(ri, rs) - query(le - 1, rs))%(1<<i); r[i][now]++; int k = 0; if (pre == 0)k = 1; else if (now == 0)k = -1; cnt += c[i][0] * k; update(b, ro[b] ? -1 : 1, rs); ro[b] ^= 1; } update(b, ro[b] ? -1 : 1, rs); ro[b] ^= 1; } printf("%lld\n", cnt * 4 + 1); } return 0; }

Compilation message (stderr)

collecting.cpp: In function 'int main()':
collecting.cpp:24:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
collecting.cpp:30:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...