oj.uz

Submission #34116

# Submission time Handle Problem Language Result Execution time Memory
34116 2017-11-07T15:26:28 Z natsukagami 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1396 ms 18560 KB 
#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.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1333 ms 18560 KB Output is correct
2 Correct 1233 ms 18560 KB Output is correct
3 Correct 1203 ms 18560 KB Output is correct
4 Correct 1243 ms 18560 KB Output is correct
5 Correct 1326 ms 18560 KB Output is correct
6 Correct 1233 ms 18560 KB Output is correct
7 Correct 1323 ms 18560 KB Output is correct
8 Correct 1296 ms 18560 KB Output is correct
9 Correct 1276 ms 18560 KB Output is correct
10 Correct 1396 ms 18560 KB Output is correct
11 Correct 1206 ms 18560 KB Output is correct
12 Correct 1233 ms 18560 KB Output is correct
13 Correct 1136 ms 18560 KB Output is correct