답안 #198409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198409	2020-01-25T23:22:23 Z	tincamatei	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	2282 ms	52900 KB

collecting

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 20;

long long quadFullNodes;
int cnt[2][(1 << (MAX_N + 1))];
int fullNodes[2][1+MAX_N];

void update(int aint, int poz, int dep, int l, int r, int nod = 1) {
	if(r < l || poz < l || r < poz) return;

	if(cnt[aint][nod] == 0 || cnt[aint][nod] == r - l + 1) {
		quadFullNodes -= fullNodes[1-aint][dep];
		fullNodes[aint][dep]--;
	}

	if(l < r) {
		int mid = (l + r) / 2;
		update(aint, poz, dep + 1, l, mid, 2 * nod);
		update(aint, poz, dep + 1, mid + 1, r, 2 * nod + 1);
		cnt[aint][nod] = cnt[aint][2 * nod] + cnt[aint][2 * nod + 1];
	} else
		cnt[aint][nod] ^= 1;

	if(cnt[aint][nod] == 0 || cnt[aint][nod] == r - l + 1) {
		quadFullNodes += fullNodes[1-aint][dep];
		fullNodes[aint][dep]++;
	}
}

int main() {
	int N, Q;
	long long fullQuad = 0;
	
	scanf("%d%d", &N, &Q);
	for(int i = 0; i <= N; ++i) {
		fullNodes[0][i] = fullNodes[1][i] = (1 << i);
		fullQuad += (1LL << (2 * i));
	}
	quadFullNodes = fullQuad;

	for(int i = 0; i < Q; ++i) {
		int t, x;
		scanf("%d%d", &t, &x);
		update(t, x, 0, 1, (1 << N));
		printf("%lld\n", (fullQuad - quadFullNodes) * 4 + 1);
	}

	return 0;
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
collecting.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t, &x);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	3 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct

Subtask #3

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2133 ms	52900 KB	Output is correct
2	Correct	2159 ms	51792 KB	Output is correct
3	Correct	1935 ms	41732 KB	Output is correct
4	Correct	2178 ms	52016 KB	Output is correct
5	Correct	2282 ms	51512 KB	Output is correct
6	Correct	2194 ms	50340 KB	Output is correct
7	Correct	2158 ms	51760 KB	Output is correct
8	Correct	2157 ms	51700 KB	Output is correct
9	Correct	1857 ms	40460 KB	Output is correct
10	Correct	1947 ms	41896 KB	Output is correct
11	Correct	2075 ms	50084 KB	Output is correct
12	Correct	2070 ms	49220 KB	Output is correct
13	Correct	1929 ms	40880 KB	Output is correct