oj.uz

답안 #12963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12963 2015-01-21T19:53:05 Z ainta 즐거운 사진 수집 (JOI13_collecting) C++
0 / 100
 0 ms 17472 KB 
#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());
	}
}

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -