oj.uz

Submission #1054115

# Submission time Handle Problem Language Result Execution time Memory
1054115 2024-08-12T06:33:51 Z juicy 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 733 ms 62036 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 21;

int n, q;
int s[2][1 << N], cnt[2][N];

void upd(int *s, int *cnt, int i, int id = 1, int l = 1, int r = 1 << n, int lvl = 0) {
  if (l == r) {
    s[id] ^= 1;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(s, cnt, i, id * 2, l, md, lvl + 1);
  } else {
    upd(s, cnt, i, id * 2 + 1, md + 1, r, lvl + 1);
  }
  if (~s[id]) {
    --cnt[lvl];
  }
  s[id] = s[id * 2] == s[id * 2 + 1] ? s[id * 2] : -1;
  if (~s[id]) {
    ++cnt[lvl];
  }
}

long long qry() {
  long long res = 0;
  for (int i = 0; i <= n; ++i) {
    res += (1LL << 2 * i) - (long long) cnt[0][i] * cnt[1][i];
  }
  return res * 4 + 1;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 0; i <= n; ++i) {
    for (auto it : {0, 1}) {
      cnt[it][i] = 1 << i;
    } 
  }
  while (q--) {
    int t, x; cin >> t >> x;
    upd(s[t], cnt[t], x);
    cout << qry() << "\n";
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2408 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 44116 KB Output is correct
2 Correct 660 ms 61572 KB Output is correct
3 Correct 593 ms 51028 KB Output is correct
4 Correct 649 ms 62036 KB Output is correct
5 Correct 697 ms 61524 KB Output is correct
6 Correct 661 ms 60200 KB Output is correct
7 Correct 676 ms 61628 KB Output is correct
8 Correct 733 ms 61556 KB Output is correct
9 Correct 559 ms 49628 KB Output is correct
10 Correct 589 ms 52052 KB Output is correct
11 Correct 619 ms 60248 KB Output is correct
12 Correct 675 ms 60372 KB Output is correct
13 Correct 630 ms 52160 KB Output is correct