Submission #77516

#TimeUsernameProblemLanguageResultExecution timeMemory
77516zubec즐거운 사진 수집 (JOI13_collecting)C++14
100 / 100
1516 ms48224 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; int cnt[2][25], t[2][(1<<21) + 100], n; inline void upd(int id, int pos){ int v = (1<<n)+pos; int sz = 1; int deep = n; t[id][v] ^= 1; v>>=1; sz += sz; --deep; while(v){ if (t[id][v] % sz == 0){ --cnt[id][deep]; } t[id][v] = t[id][v+v] + t[id][v+v+1]; if (t[id][v] % sz == 0) ++cnt[id][deep]; v>>=1; sz += sz; --deep; } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int tt; cin >> n >> tt; for (int i = 0; i <= n; i++) cnt[0][i] = cnt[1][i] = (1<<i); while(tt--){ int type, x; cin >> type >> x; --x; if (type == 0){ upd(0, x); } else { upd(1, x); } //ll ans = ((1<<n)*(1<<n)-1)/3; ll ans = (1ll<<n)*(1ll<<n); //cout << "kek " << ans << ' '; for (int i = 0; i < n; i++){ ans -= (ll)cnt[0][i]*(ll)cnt[1][i]*3; //cout << i << ' ' << cnt[0][i] << ' ' << cnt[1][i] << endl; } cout << 4*(ans-1)/3+1 << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...