#include<stdio.h>
long long Res, D[21];
int C[2][21];
int n, Q, IT[2][2097152];
void Do(int ck, int a){
a += (1 << n);
int h1 = 0, h2 = 0, c = 0, i;
IT[ck][a] = !IT[ck][a];
while (a != 1){
c++; a >>= 1;
if (IT[ck][a] == (1 << c) || IT[ck][a] == 0)h1 = c;
IT[ck][a] = IT[ck][a * 2] + IT[ck][a * 2 + 1];
if (IT[ck][a] == (1 << c) || IT[ck][a] == 0)h2 = c;
}
if (h1){
C[ck][h1]--;
C[ck][0]++;
for (i = 0; i < h1; i++)C[ck][i]++;
}
else{
C[ck][h2]++;
C[ck][0]--;
for (i = 0; i < h2; i++)C[ck][i]--;
}
}
long long Calc(){
int i, S = 0;
long long r = 0;
for (i = n; i >= 1; i--){
S += C[1][i] << i;
r += C[0][i] * D[i] * (S >> i);
}
return r;
}
int main()
{
int ck, a, i;
scanf("%d%d", &n, &Q);
C[0][n] = C[1][n] = 1;
for (i = 1; i <= 20; i++)D[i] = (D[i - 1] + 1) * 4;
while (Q--){
scanf("%d%d", &ck, &a);
a--;
Do(ck, a);
printf("%lld\n", D[n] + 1 - Calc());
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17472 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
17472 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
