oj.uz

Submission #34010

# Submission time Handle Problem Language Result Execution time Memory
34010 2017-11-06T04:44:11 Z cheater2k 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2533 ms 67712 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = (1 << 21);

int n, q;
int t, x;
int T[2][N << 2];
int cnt[2][22][2];

#define mid ((l + r) >> 1)
void upd(int type, int v, int l, int r, int pos, int layer) {
	if (l > r || pos < l || pos > r) return;
	if (l == r) {
		cnt[type][layer][T[type][v]]--; T[type][v] ^= 1; cnt[type][layer][T[type][v]]++; return;
	}
	upd(type, v << 1, l, mid, pos, layer - 1);
	upd(type, v << 1 | 1, mid + 1, r, pos, layer - 1);

	int old = T[type][v]; 
	if (old != -1) cnt[type][layer][old]--;
	T[type][v] = (T[type][v << 1] == T[type][v << 1 | 1] && T[type][v << 1] != -1) ? T[type][v << 1] : -1;
	if (T[type][v] != -1) cnt[type][layer][T[type][v]]++;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q;
	long long ans = 0;
	for (int i = n * 2; i >= 0; i -= 2) ans += (1LL << i);
	cnt[0][n][0] = cnt[1][n][0] = 1;
	for (int i = n - 1; i >= 0; --i) cnt[0][i][0] = cnt[1][i][0] = (1 << n-i);

	while(q--) {
		cin >> t >> x; --x;
		upd(t, 1, 0, (1 << n) - 1, x, n);

		long long cur = 0;
		for (int i = n; i >= 1; --i) {
			cur += 1LL * cnt[0][i][0] * cnt[1][i][0];
			cur += 1LL * cnt[0][i][0] * cnt[1][i][1];
			cur += 1LL * cnt[0][i][1] * cnt[1][i][0];
			cur += 1LL * cnt[0][i][1] * cnt[1][i][1]; 
		}

		printf("%lld\n", ans - cur * 4);
	}
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:32:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  for (int i = n - 1; i >= 0; --i) cnt[0][i][0] = cnt[1][i][0] = (1 << n-i);
                                                                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 67712 KB Output is correct
2 Correct 0 ms 67712 KB Output is correct
3 Correct 0 ms 67712 KB Output is correct
4 Correct 0 ms 67712 KB Output is correct
5 Correct 0 ms 67712 KB Output is correct
6 Correct 0 ms 67712 KB Output is correct
7 Correct 0 ms 67712 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 67712 KB Output is correct
2 Correct 0 ms 67712 KB Output is correct
3 Correct 0 ms 67712 KB Output is correct
4 Correct 0 ms 67712 KB Output is correct
5 Correct 0 ms 67712 KB Output is correct
6 Correct 0 ms 67712 KB Output is correct
7 Correct 0 ms 67712 KB Output is correct
8 Correct 0 ms 67712 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2286 ms 67712 KB Output is correct
2 Correct 2456 ms 67712 KB Output is correct
3 Correct 2163 ms 67712 KB Output is correct
4 Correct 2523 ms 67712 KB Output is correct
5 Correct 2389 ms 67712 KB Output is correct
6 Correct 2426 ms 67712 KB Output is correct
7 Correct 2533 ms 67712 KB Output is correct
8 Correct 2319 ms 67712 KB Output is correct
9 Correct 1876 ms 67712 KB Output is correct
10 Correct 1883 ms 67712 KB Output is correct
11 Correct 2426 ms 67712 KB Output is correct
12 Correct 2276 ms 67712 KB Output is correct
13 Correct 2416 ms 67712 KB Output is correct