Submission #12964

#	Time	Username	Problem	Language	Result	Execution time	Memory
12964		ainta	즐거운 사진 수집 (JOI13_collecting)	C++98	100 / 100	1712 ms	17472 KiB

collecting

#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);
	}
	S = 0;
	for (i = n; i >= 1; i--){
		r += C[1][i] * D[i] * (S >> i);
		S += C[0][i] << 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());
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70