oj.uz

Submission #803647

# Submission time Handle Problem Language Result Execution time Memory
803647 2023-08-03T05:15:59 Z GEN 이지후(#10137) Vera and Modern Art (CCO17_art) C++17
25 / 25
 1231 ms 369796 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXT = 12000005;
const int MAXN = 200005;
struct bit {
	int tree[MAXN];
	void add(int x, int v) {
		for (int i = x + 2; i < MAXN; i += i & -i)
			tree[i] += v;
	}
	int query(int x) {
		int ret = 0;
		for (int i = x + 2; i; i -= i & -i)
			ret += tree[i];
		return ret;
	}
} bit;

int trie[2][MAXT][2], piv[2], mark[2][MAXT];
int din[2][MAXT], dout[2][MAXT], pivs;

void dfs(int tr, int pos) {
	din[tr][pos] = pivs;
	if (mark[tr][pos]) {
		pivs++;
	}
	for (int i = 0; i < 2; i++) {
		if (trie[tr][pos][i])
			dfs(tr, trie[tr][pos][i]);
	}
	dout[tr][pos] = pivs;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	vector<pi> crd(n);
	vector<int> weights(n);
	for (int i = 0; i < n; i++) {
		lint x[2];
		cin >> x[0] >> x[1] >> weights[i];
		for (int j = 0; j < 2; j++) {
			int pos = 0;
			while (x[j] > 1) {
				if (!trie[j][pos][x[j] & 1]) {
					trie[j][pos][x[j] & 1] = ++piv[j];
				}
				pos = trie[j][pos][x[j] & 1];
				x[j] >>= 1;
			}
			crd[i][j] = pos;
		}
	}
	vector<array<int, 3>> query(q);
	for (int i = 0; i < q; i++) {
		lint x[2];
		cin >> x[0] >> x[1];
		for (int j = 0; j < 2; j++) {
			int pos = 0;
			while (x[j] > 1) {
				if (!trie[j][pos][x[j] & 1]) {
					break;
				}
				pos = trie[j][pos][x[j] & 1];
				x[j] >>= 1;
			}
			query[i][j] = pos;
			mark[j][query[i][j]] = 1;
		}
		query[i][2] = i;
	}
	for (int i = 0; i < 2; i++)
		dfs(i, 0), pivs = 0;
	vector<vector<pi>> points(q + 1);
	vector<vector<pi>> queries(q + 1);
	vector<lint> ans(q);
	for (int i = 0; i < n; i++) {
		points[din[0][crd[i][0]]].push_back({din[1][crd[i][1]], weights[i]});
		points[din[0][crd[i][0]]].push_back({dout[1][crd[i][1]], -weights[i]});
		points[dout[0][crd[i][0]]].push_back({din[1][crd[i][1]], -weights[i]});
		points[dout[0][crd[i][0]]].push_back({dout[1][crd[i][1]], +weights[i]});
	}
	for (int i = 0; i < q; i++) {
		queries[din[0][query[i][0]]].push_back({din[1][query[i][1]], i});
	}
	for (int i = 0; i <= q; i++) {
		for (auto &[j, w] : points[i])
			bit.add(j, w);
		for (auto &[j, idx] : queries[i])
			ans[idx] = bit.query(j);
	}
	for (int i = 0; i < q; i++)
		cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 4628 KB Output is correct
3 Correct 7 ms 4508 KB Output is correct
4 Correct 4 ms 2004 KB Output is correct
5 Correct 4 ms 2004 KB Output is correct
6 Correct 4 ms 2388 KB Output is correct
7 Correct 4 ms 2388 KB Output is correct
8 Correct 4 ms 2388 KB Output is correct
9 Correct 5 ms 2388 KB Output is correct
10 Correct 4 ms 2388 KB Output is correct
11 Correct 4 ms 2452 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 204548 KB Output is correct
2 Correct 677 ms 204544 KB Output is correct
3 Correct 475 ms 92204 KB Output is correct
4 Correct 455 ms 92396 KB Output is correct
5 Correct 362 ms 102468 KB Output is correct
6 Correct 358 ms 102340 KB Output is correct
7 Correct 360 ms 102396 KB Output is correct
8 Correct 378 ms 102340 KB Output is correct
9 Correct 379 ms 102672 KB Output is correct
10 Correct 358 ms 102532 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 301 ms 71700 KB Output is correct
3 Correct 269 ms 71672 KB Output is correct
4 Correct 156 ms 34244 KB Output is correct
5 Correct 154 ms 34328 KB Output is correct
6 Correct 125 ms 35556 KB Output is correct
7 Correct 123 ms 35544 KB Output is correct
8 Correct 134 ms 35560 KB Output is correct
9 Correct 130 ms 35684 KB Output is correct
10 Correct 121 ms 35596 KB Output is correct
11 Correct 144 ms 35604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 4628 KB Output is correct
3 Correct 7 ms 4508 KB Output is correct
4 Correct 4 ms 2004 KB Output is correct
5 Correct 4 ms 2004 KB Output is correct
6 Correct 4 ms 2388 KB Output is correct
7 Correct 4 ms 2388 KB Output is correct
8 Correct 4 ms 2388 KB Output is correct
9 Correct 5 ms 2388 KB Output is correct
10 Correct 4 ms 2388 KB Output is correct
11 Correct 4 ms 2452 KB Output is correct
12 Correct 696 ms 204548 KB Output is correct
13 Correct 677 ms 204544 KB Output is correct
14 Correct 475 ms 92204 KB Output is correct
15 Correct 455 ms 92396 KB Output is correct
16 Correct 362 ms 102468 KB Output is correct
17 Correct 358 ms 102340 KB Output is correct
18 Correct 360 ms 102396 KB Output is correct
19 Correct 378 ms 102340 KB Output is correct
20 Correct 379 ms 102672 KB Output is correct
21 Correct 358 ms 102532 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 301 ms 71700 KB Output is correct
24 Correct 269 ms 71672 KB Output is correct
25 Correct 156 ms 34244 KB Output is correct
26 Correct 154 ms 34328 KB Output is correct
27 Correct 125 ms 35556 KB Output is correct
28 Correct 123 ms 35544 KB Output is correct
29 Correct 134 ms 35560 KB Output is correct
30 Correct 130 ms 35684 KB Output is correct
31 Correct 121 ms 35596 KB Output is correct
32 Correct 144 ms 35604 KB Output is correct
33 Correct 1231 ms 369760 KB Output is correct
34 Correct 1225 ms 369796 KB Output is correct
35 Correct 773 ms 142828 KB Output is correct
36 Correct 726 ms 143676 KB Output is correct
37 Correct 616 ms 164268 KB Output is correct
38 Correct 674 ms 164476 KB Output is correct
39 Correct 642 ms 164404 KB Output is correct
40 Correct 595 ms 164260 KB Output is correct
41 Correct 608 ms 164448 KB Output is correct
42 Correct 649 ms 163972 KB Output is correct