Submission #34116

#	Time	Username	Problem	Language	Result	Execution time	Memory
34116		natsukagami	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	1396 ms	18560 KiB

collecting

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int N, Q;

struct IT {
	int sum[25]; ll all = 0;
	int tree[1 << 21];
	void init() {
		for (int i = 0; i <= N; ++i) sum[i] = (1 << (N - i));
	}
	void upd(int node, int ln, int mul = 1) {
		if (tree[node] == 0 || tree[node] == (1 << ln)) {
			sum[ln] += mul;
		} else all += mul * (1 << (N - ln));
	}
	void flip(int pos) {
		int val = tree[pos + (1 << N)] ? -1 : 1;
		for (int i = pos + (1 << N), ln = 0; i; i >>= 1, ++ln) {
			upd(i, ln, -1);
			tree[i] += val;
			upd(i, ln, 1);
		}
	}
} Row, Col;

ll val[25];

void read(int &x) {
	x = 0; int ch = 0;
	while (ch < '0' || ch > '9') ch = getchar_unlocked();
	do { x = (x << 3) + (x << 1) + ch - '0'; 
		ch = getchar_unlocked(); } while (ch >= '0' && ch <= '9');
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	read(N); read(Q);
	Row.init(); Col.init();
	while (Q--) {
		int typ, id; read(typ); read(id); --id;
		(typ ? Col : Row).flip(id);
		val[0] = (1 << N);
		for (int i = 1; i <= N; ++i) {
			val[i] = val[i - 1] * 2 + (1 << (N - i)) - 4LL * Row.sum[i];
		}
		// for (int i = 0; i <= N; ++i)
		// 	cout << i << ' ' << val[i] << endl;
		ll ans = Col.all, cur = 0;
		for (int i = N; i >= 0; --i) {
			ll num = Col.sum[i] - cur;
			cur = (cur + num) << 1;
			ans += num * val[i];
			// cout << i << ' ' << num << ' ' << ans << endl;
		}
		printf("%lld\n", ans);
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70