제출 #377770

#제출 시각아이디문제언어결과실행 시간메모리
377770RyoPham즐거운 사진 수집 (JOI13_collecting)C++17
100 / 100
1984 ms70252 KiB
#define taskname "test" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define fi first #define se second typedef long long lli; typedef pair<int, int> pii; const int maxn = 2e6 + 5; const int logn = 22; int n, Q; struct segment_tree { int cnt_one[maxn * 4], cnt_diff[logn]; int leaf_id[maxn]; void build(int x, int l, int r) { if(l == r) { leaf_id[l] = x; return; } int mid = (l + r) / 2; build(x * 2, l, mid); build(x * 2 + 1, mid + 1, r); } void update(int x, int l, int r, int p, int lv) { if(l == r) { cnt_one[x] ^= 1; return; } int mid = (l + r) / 2; if(p <= mid) update(x * 2, l, mid, p, lv + 1); else update(x * 2 + 1, mid + 1, r, p, lv + 1); if(cnt_one[x] > 0 && cnt_one[x] < r - l + 1) --cnt_diff[lv]; cnt_one[x] = cnt_one[x * 2] + cnt_one[x * 2 + 1]; if(cnt_one[x] > 0 && cnt_one[x] < r - l + 1) ++cnt_diff[lv]; } } row_data, col_data; void read_input() { cin >> n >> Q; cerr << n << ' ' << Q; } void query(segment_tree&row, segment_tree&col, int x, lli&k) { int lv = n, cur_size = 1, cur = row.leaf_id[x]; while(lv >= 0) { if(row.cnt_one[cur] > 0 && row.cnt_one[cur] < cur_size) k -= (1 << lv); else k -= col.cnt_diff[lv]; --lv; cur /= 2; cur_size *= 2; } row.update(1, 1, (1 << n), x, 0); lv = n; cur_size = 1; cur = row.leaf_id[x]; while(lv >= 0) { if(row.cnt_one[cur] > 0 && row.cnt_one[cur] < cur_size) k += (1 << lv); else k += col.cnt_diff[lv]; --lv; cur /= 2; cur_size *= 2; } } void solve() { row_data.build(1, 1, (1 << n)); col_data.build(1, 1, (1 << n)); lli k = 0; for(; Q > 0; --Q) { int type, x; cin >> type >> x; if(type == 0) query(row_data, col_data, x, k); else query(col_data, row_data, x, k); cout << k * 4 + 1 << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read_input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...