oj.uz

Submission #426684

# Submission time Handle Problem Language Result Execution time Memory
426684 2021-06-14T08:59:50 Z palilo 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1312 ms 61908 KB 
#include <bits/stdc++.h>
using namespace std;

class segtree {
	const int n;
	vector<int> tree, cnt;

public:
	segtree(int _n) : n(_n), tree(1 << (n + 1)), cnt(n + 1) {
		for (int i = 0; i <= n; ++i)
			cnt[i] = 1 << i;
	}

	int& operator[](int i) { return cnt[i]; }
	void flip(int i) {
		int val = tree[i += 1 << n] ? -1 : 1;
		for (int d = n; i; i >>= 1, --d) {
			if (tree[i] == 0 || tree[i] == 1 << (n - d)) --cnt[d];
			tree[i] += val;
			if (tree[i] == 0 || tree[i] == 1 << (n - d)) ++cnt[d];
		}
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif

	int n, q;
	cin >> n >> q;

	int64_t total = 0; // # of nodes
	for (int i = 0; i <= n; ++i)
		total += 1ll * (1 << i) * (1 << i);

	segtree row(n), col(n);

	for (int i; q--;) {
		char c;
		cin >> c >> i, --i;
		(c == '0' ? row : col).flip(i);

		int64_t grey = total;
		for (int i = 0; i <= n; ++i)
			grey -= 1ll * row[i] * col[i];
		cout << grey * 4 + 1 << '\n';
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1298 ms 44112 KB Output is correct
2 Correct 1220 ms 61644 KB Output is correct
3 Correct 1055 ms 50528 KB Output is correct
4 Correct 1253 ms 61908 KB Output is correct
5 Correct 1236 ms 61396 KB Output is correct
6 Correct 1307 ms 60272 KB Output is correct
7 Correct 1312 ms 61568 KB Output is correct
8 Correct 1096 ms 61568 KB Output is correct
9 Correct 1052 ms 49240 KB Output is correct
10 Correct 959 ms 51788 KB Output is correct
11 Correct 1109 ms 60440 KB Output is correct
12 Correct 1047 ms 60404 KB Output is correct
13 Correct 946 ms 51732 KB Output is correct