oj.uz

Submission #622942

# Submission time Handle Problem Language Result Execution time Memory
622942 2022-08-04T21:02:58 Z izanbf Examination (JOI19_examination) C++14
0 / 100
 3000 ms 11340 KB 
#include <bits/stdc++.h>
using namespace std;

#define D(x) cerr << #x << " = " << x << ", "

struct Point {
	int x, y, z;
};

struct Query {
	int a, b, c, id;
};

const int B = 300;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int N, Q;
	cin >> N >> Q;

	vector<Point> pts(N);
	for (int i = 0; i < N; ++i) {
		Point& p = pts[i];
		cin >> p.x >> p.y;
		p.z = p.x + p.y;
	}

	vector<Query> qs(Q);
	for (int i = 0; i < Q; ++i) {
		Query& q = qs[i];
		cin >> q.a >> q.b >> q.c;
		q.id = i;
	}

	sort(qs.begin(), qs.end(), [](const Query& q, const Query& p) {
		return q.c < p.c;
	});

	sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
		return a.z < b.z;
	});

	int blocks = (N+B-1)/B;
	vector<vector<int>> block_queries(blocks);
	int j = 0;

	for (int block = 1; block < blocks; ++block) {
		int i = B*block;
		while (j < Q and qs[j].c < pts[i].z) {
			block_queries[block-1].push_back(j);
			++j;
		}
	}
	while (j < Q) {
		block_queries.back().push_back(j);
		++j;
	}

	vector<int> ans(Q);

	for (int block = 0; block < blocks; ++block) {
		if (block_queries[block].empty()) continue;

		multiset<int> heights;

		vector<int> in_block;
		in_block.reserve(B);
		for (int i = B*block; i < N and i < B*(block+1); ++i) {
			in_block.push_back(i);
		}

		vector<int> over_block;
		over_block.reserve(N-B*block);
		for (int i = B*(block+1); i < N; ++i) {
			over_block.push_back(i);
			heights.insert(pts[i].y);
		}

		sort(over_block.begin(), over_block.end(), [&](int l, int r) {
			return pts[l].x > pts[r].x;
		});

		sort(block_queries[block].begin(), block_queries[block].end(), [&](int l, int r) {
			return qs[l].a < qs[r].a;
		});

		for (int i : block_queries[block]) {
			Query& q = qs[i];

			int cnt_in = 0, cnt_over = 0;

			// points in block
			for (int k : in_block) {
				Point& p = pts[k];
				if (p.x >= q.a and p.y >= q.b and p.z >= q.c) ++cnt_in;
			}

			// points over block
			while (not over_block.empty() and pts[over_block.back()].x < q.a) {
				Point& p = pts[over_block.back()];
				heights.erase(heights.find(p.y));
				over_block.pop_back();
			}

			for (int y : heights) {
				if (y >= q.b) {
					++cnt_over;
				}
			}

			// D(q.id), D(block), D(in_block.size()), D(over_block.size()), D(cnt_in), D(cnt_over) << endl;

			ans[q.id] = cnt_in + cnt_over;
		}
	}

	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 29 ms 712 KB Output is correct
8 Correct 27 ms 712 KB Output is correct
9 Correct 32 ms 716 KB Output is correct
10 Correct 25 ms 672 KB Output is correct
11 Correct 21 ms 588 KB Output is correct
12 Incorrect 21 ms 596 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 29 ms 712 KB Output is correct
8 Correct 27 ms 712 KB Output is correct
9 Correct 32 ms 716 KB Output is correct
10 Correct 25 ms 672 KB Output is correct
11 Correct 21 ms 588 KB Output is correct
12 Incorrect 21 ms 596 KB Output isn't correct
13 Halted 0 ms 0 KB -