Submission #34010

#	Time	Username	Problem	Language	Result	Execution time	Memory
34010		cheater2k	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	2533 ms	67712 KiB

collecting

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

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