Submission #198409

#	Time	Username	Problem	Language	Result	Execution time	Memory
198409		tincamatei	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	2282 ms	52900 KiB

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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70