oj.uz

Submission #803636

# Submission time Handle Problem Language Result Execution time Memory
803636 2023-08-03T05:12:30 Z GEN 이지후(#10137) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 175340 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;

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<array<int, 5>> rect(n);
	for (int i = 0; i < n; i++) {
		rect[i][0] = din[0][crd[i][0]];
		rect[i][1] = dout[0][crd[i][0]];
		rect[i][2] = din[1][crd[i][1]];
		rect[i][3] = dout[1][crd[i][1]];
		rect[i][4] = weights[i];
	}
	for (int i = 0; i < q; i++) {
		query[i][0] = din[0][query[i][0]];
		query[i][1] = din[1][query[i][1]];
	}
	for (int i = 0; i < q; i++) {
		lint ans = 0;
		for (auto &[x1, y1, x2, y2, w] : rect) {
			if (x1 <= query[i][0] && y1 > query[i][0] && x2 <= query[i][1] && y2 > query[i][1])
				ans += w;
		}
		cout << ans << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 19 ms 4300 KB Output is correct
3 Correct 16 ms 4180 KB Output is correct
4 Correct 15 ms 1748 KB Output is correct
5 Correct 15 ms 1716 KB Output is correct
6 Correct 15 ms 2100 KB Output is correct
7 Correct 15 ms 2088 KB Output is correct
8 Correct 15 ms 2004 KB Output is correct
9 Correct 15 ms 2004 KB Output is correct
10 Correct 14 ms 2004 KB Output is correct
11 Correct 15 ms 2068 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 175340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 4074 ms 56948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 19 ms 4300 KB Output is correct
3 Correct 16 ms 4180 KB Output is correct
4 Correct 15 ms 1748 KB Output is correct
5 Correct 15 ms 1716 KB Output is correct
6 Correct 15 ms 2100 KB Output is correct
7 Correct 15 ms 2088 KB Output is correct
8 Correct 15 ms 2004 KB Output is correct
9 Correct 15 ms 2004 KB Output is correct
10 Correct 14 ms 2004 KB Output is correct
11 Correct 15 ms 2068 KB Output is correct
12 Execution timed out 4050 ms 175340 KB Time limit exceeded
13 Halted 0 ms 0 KB -