#include<bits/stdc++.h>
using namespace std;
#define maxn 25
#define int long long
int n,q,c[2][maxn][(1<<20)+5],num[2][maxn],sum,ans;
void update(int p,int x){
c[p][0][x]^=1;ans=0;
for(int i=1;i<=n;i++){
x>>=1;int pre=c[p][i][x];
if(c[p][i-1][x<<1|1]==c[p][i-1][x<<1]) c[p][i][x]=c[p][i-1][x<<1];
else c[p][i][x]=-1;
if(pre!=-1 && c[p][i][x]==-1) num[p][i]--;
if(pre==-1 && c[p][i][x]!=-1) num[p][i]++;
ans+=num[p][i]*num[p^1][i];
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> n >> q;
for(int i=0;i<=n;i++) sum+=(1LL<<(2*i));
for(int i=1;i<=n;i++) num[0][i]=num[1][i]=(1LL<<(n-i));
for(int i=1;i<=q;i++){
int p,x;cin >> p >> x;x--;
update(p,x);
cout << sum-4*ans << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
464 KB |
Output is correct |
3 |
Correct |
1 ms |
464 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
857 ms |
78404 KB |
Output is correct |
2 |
Correct |
914 ms |
78388 KB |
Output is correct |
3 |
Correct |
784 ms |
59136 KB |
Output is correct |
4 |
Correct |
865 ms |
78596 KB |
Output is correct |
5 |
Correct |
862 ms |
78180 KB |
Output is correct |
6 |
Correct |
918 ms |
77060 KB |
Output is correct |
7 |
Correct |
914 ms |
78280 KB |
Output is correct |
8 |
Correct |
995 ms |
78348 KB |
Output is correct |
9 |
Correct |
896 ms |
57764 KB |
Output is correct |
10 |
Correct |
865 ms |
60332 KB |
Output is correct |
11 |
Correct |
993 ms |
77000 KB |
Output is correct |
12 |
Correct |
1035 ms |
77108 KB |
Output is correct |
13 |
Correct |
848 ms |
60152 KB |
Output is correct |