oj.uz

Submission #622960

# Submission time Handle Problem Language Result Execution time Memory
622960 2022-08-04T21:58:16 Z izanbf Examination (JOI19_examination) C++14
2 / 100
 3000 ms 22804 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;
 
		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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 34 ms 2224 KB Output is correct
8 Correct 33 ms 2224 KB Output is correct
9 Correct 33 ms 2132 KB Output is correct
10 Correct 29 ms 1748 KB Output is correct
11 Correct 25 ms 1760 KB Output is correct
12 Correct 24 ms 660 KB Output is correct
13 Correct 47 ms 2112 KB Output is correct
14 Correct 44 ms 1940 KB Output is correct
15 Correct 45 ms 1876 KB Output is correct
16 Correct 25 ms 1108 KB Output is correct
17 Correct 22 ms 1452 KB Output is correct
18 Correct 5 ms 596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 22804 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 3072 ms 22804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 34 ms 2224 KB Output is correct
8 Correct 33 ms 2224 KB Output is correct
9 Correct 33 ms 2132 KB Output is correct
10 Correct 29 ms 1748 KB Output is correct
11 Correct 25 ms 1760 KB Output is correct
12 Correct 24 ms 660 KB Output is correct
13 Correct 47 ms 2112 KB Output is correct
14 Correct 44 ms 1940 KB Output is correct
15 Correct 45 ms 1876 KB Output is correct
16 Correct 25 ms 1108 KB Output is correct
17 Correct 22 ms 1452 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Execution timed out 3072 ms 22804 KB Time limit exceeded
20 Halted 0 ms 0 KB -