Submission #622942

#	Time	Username	Problem	Language	Result	Execution time	Memory
622942		izanbf	Examination (JOI19_examination)	C++14	0 / 100	3059 ms	11340 KiB

examination

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57