Submission #622960

#	Time	Username	Problem	Language	Result	Execution time	Memory
622960		izanbf	Examination (JOI19_examination)	C++14	2 / 100	3072 ms	22804 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;
 
		set<int> values;

	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;
		values.insert(p.x);
		values.insert(p.y);
		values.insert(p.z);
	}

	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;
		values.insert(q.a);
		values.insert(q.b);
		values.insert(q.c);
	}


	unordered_map<int,int> comp;
	for (int v : values) {
		comp[v] = comp.size();
	}

	for (Query& q : qs) {
		q.a = comp[q.a];
		q.b = comp[q.b];
		q.c = comp[q.c];
	}

	for (Point& p : pts) {
		p.x = comp[p.x];
		p.y = comp[p.y];
		p.z = comp[p.z];
	}

	int sz = comp.size() + 2;
 
	sort(qs.begin(), qs.end(), [](const Query& l, const Query& r) {
		return l.c < r.c;
	});
 
	sort(pts.begin(), pts.end(), [](const Point& l, const Point& r) {
		return l.z < r.z;
	});
 
	int blocks = (N+B-1)/B;
	vector<vector<Query>> 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(qs[j]);
			++j;
		}
	}
	while (j < Q) {
		block_queries.back().push_back(qs[j]);
		++j;
	}
 
	vector<int> ans(Q);
 
	for (int block = 0; block < blocks; ++block) {
		if (block_queries[block].empty()) continue;
 
		multiset<int> heights;
 
		vector<Point> in_block;
		in_block.reserve(B);
		for (int i = B*block; i < N and i < B*(block+1); ++i) {
			in_block.push_back(pts[i]);
		}
 
		vector<Point> over_block;
		over_block.reserve(N-B*block);
		for (int i = B*(block+1); i < N; ++i) {
			over_block.push_back(pts[i]);
			heights.insert(pts[i].y);
		}
 
		sort(over_block.begin(), over_block.end(), [&](const Point& l, const Point& r) {
			return l.x > r.x;
		});
 
		sort(block_queries[block].begin(), block_queries[block].end(), [&](const Query& l, const Query& r) {
			return l.a < r.a;
		});
 
		for (const Query& q : block_queries[block]) {
			int cnt_in = 0;
			int cnt_over = 0;
 
			// points in block
			for (const Point& p : in_block) {
				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 over_block.back().x < q.a) {
				const Point& p = 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';
	}
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:63:6: warning: unused variable 'sz' [-Wunused-variable]
   63 |  int sz = comp.size() + 2;
      |      ^~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57