oj.uz

Submission #198409

# Submission time Handle Problem Language Result Execution time Memory
198409 2020-01-25T23:22:23 Z tincamatei 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2282 ms 52900 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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