oj.uz

Submission #1104393

# Submission time Handle Problem Language Result Execution time Memory
1104393 2024-10-23T15:10:25 Z fryingduc 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 935 ms 78440 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = (1 << 20) + 5;
int n, q;

struct segment_tree {
  int n;
  vector<int> tree;
  vector<int> cnt;
  segment_tree() {}
  segment_tree(int n) : n(n), tree(n * 4 + 6), cnt(21, 0) {
    for(int i = 0; i < 21; ++i) {
      cnt[i] = (1 << i);
    }    
  }
  void update(int ind, int l, int r, int pos, int dep) {
    if(l == r) {
      tree[ind] ^= 1;
      return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ind << 1, l, mid, pos, dep + 1);
    else update(ind << 1 | 1, mid + 1, r, pos, dep + 1);
    
    if(tree[ind] != -1) --cnt[dep];
    
    if(tree[ind << 1] >= 0 and tree[ind << 1] == tree[ind << 1 | 1]) {
      tree[ind] = tree[ind << 1];
      ++cnt[dep];
    }
    else {
      tree[ind] = -1;
    }
  }
  void update(int pos) {
    update(1, 1, n, pos, 0);
  }
} st[2];
void solve() {
  cin >> n >> q;
  
  st[0] = segment_tree((1 << n));
  st[1] = segment_tree((1 << n));
  
  while(q--) {
    int t, x; cin >> t >> x;
    st[t].update(x);
    
    long long res = 0;
    for(int i = 0; i <= n; ++i) {
      res += (1ll << (i << 1));
      res -= 1ll * st[0].cnt[i] * st[1].cnt[i];
    }
//    debug(st[0].cnt);
//    debug(st[1].cnt);
    cout << res * 4 + 1 << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 78092 KB Output is correct
2 Correct 864 ms 77960 KB Output is correct
3 Correct 646 ms 58928 KB Output is correct
4 Correct 738 ms 78440 KB Output is correct
5 Correct 738 ms 77896 KB Output is correct
6 Correct 835 ms 76832 KB Output is correct
7 Correct 854 ms 78212 KB Output is correct
8 Correct 799 ms 78024 KB Output is correct
9 Correct 644 ms 57492 KB Output is correct
10 Correct 658 ms 60080 KB Output is correct
11 Correct 745 ms 76652 KB Output is correct
12 Correct 743 ms 76688 KB Output is correct
13 Correct 720 ms 59896 KB Output is correct