Submission #1104393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104393		fryingduc	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	935 ms	78440 KiB

collecting

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70