oj.uz

답안 #622969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
622969 2022-08-04T22:14:52 Z izanbf Examination (JOI19_examination) C++14
43 / 100
 3000 ms 67160 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;

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int k) {
        this->n = k;
        bit.assign(k, 0);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
 
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;

		FenwickTree ft(sz);
 
		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]);
			ft.add(pts[i].y, 1); //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();
				ft.add(p.y, -1); // heights.erase(heights.find(p.y));
				over_block.pop_back();
			}
 
			/*for (int y : heights) {
				if (y >= q.b) {
					++cnt_over;
				}
			}*/

			cnt_over = ft.sum(q.b, sz-1);
 
			// 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
2.0 / 2.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 11 ms 2188 KB Output is correct
8 Correct 12 ms 2116 KB Output is correct
9 Correct 11 ms 2132 KB Output is correct
10 Correct 9 ms 1740 KB Output is correct
11 Correct 9 ms 1620 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 9 ms 1928 KB Output is correct
14 Correct 8 ms 1876 KB Output is correct
15 Correct 8 ms 1876 KB Output is correct
16 Correct 5 ms 1108 KB Output is correct
17 Correct 6 ms 1364 KB Output is correct
18 Correct 2 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 18800 KB Output is correct
2 Correct 230 ms 18848 KB Output is correct
3 Correct 217 ms 18800 KB Output is correct
4 Correct 180 ms 15604 KB Output is correct
5 Correct 196 ms 15476 KB Output is correct
6 Correct 78 ms 6204 KB Output is correct
7 Correct 250 ms 18676 KB Output is correct
8 Correct 225 ms 18792 KB Output is correct
9 Correct 214 ms 18276 KB Output is correct
10 Correct 185 ms 14952 KB Output is correct
11 Correct 149 ms 14908 KB Output is correct
12 Correct 70 ms 6216 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 18800 KB Output is correct
2 Correct 230 ms 18848 KB Output is correct
3 Correct 217 ms 18800 KB Output is correct
4 Correct 180 ms 15604 KB Output is correct
5 Correct 196 ms 15476 KB Output is correct
6 Correct 78 ms 6204 KB Output is correct
7 Correct 250 ms 18676 KB Output is correct
8 Correct 225 ms 18792 KB Output is correct
9 Correct 214 ms 18276 KB Output is correct
10 Correct 185 ms 14952 KB Output is correct
11 Correct 149 ms 14908 KB Output is correct
12 Correct 70 ms 6216 KB Output is correct
13 Correct 2090 ms 21908 KB Output is correct
14 Correct 1617 ms 22612 KB Output is correct
15 Correct 228 ms 21308 KB Output is correct
16 Correct 1386 ms 19488 KB Output is correct
17 Correct 1233 ms 19348 KB Output is correct
18 Correct 137 ms 7752 KB Output is correct
19 Correct 2115 ms 24840 KB Output is correct
20 Correct 2057 ms 23636 KB Output is correct
21 Correct 1835 ms 24780 KB Output is correct
22 Correct 146 ms 16644 KB Output is correct
23 Correct 150 ms 16660 KB Output is correct
24 Correct 69 ms 7108 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 11 ms 2188 KB Output is correct
8 Correct 12 ms 2116 KB Output is correct
9 Correct 11 ms 2132 KB Output is correct
10 Correct 9 ms 1740 KB Output is correct
11 Correct 9 ms 1620 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 9 ms 1928 KB Output is correct
14 Correct 8 ms 1876 KB Output is correct
15 Correct 8 ms 1876 KB Output is correct
16 Correct 5 ms 1108 KB Output is correct
17 Correct 6 ms 1364 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 222 ms 18800 KB Output is correct
20 Correct 230 ms 18848 KB Output is correct
21 Correct 217 ms 18800 KB Output is correct
22 Correct 180 ms 15604 KB Output is correct
23 Correct 196 ms 15476 KB Output is correct
24 Correct 78 ms 6204 KB Output is correct
25 Correct 250 ms 18676 KB Output is correct
26 Correct 225 ms 18792 KB Output is correct
27 Correct 214 ms 18276 KB Output is correct
28 Correct 185 ms 14952 KB Output is correct
29 Correct 149 ms 14908 KB Output is correct
30 Correct 70 ms 6216 KB Output is correct
31 Correct 2090 ms 21908 KB Output is correct
32 Correct 1617 ms 22612 KB Output is correct
33 Correct 228 ms 21308 KB Output is correct
34 Correct 1386 ms 19488 KB Output is correct
35 Correct 1233 ms 19348 KB Output is correct
36 Correct 137 ms 7752 KB Output is correct
37 Correct 2115 ms 24840 KB Output is correct
38 Correct 2057 ms 23636 KB Output is correct
39 Correct 1835 ms 24780 KB Output is correct
40 Correct 146 ms 16644 KB Output is correct
41 Correct 150 ms 16660 KB Output is correct
42 Correct 69 ms 7108 KB Output is correct
43 Execution timed out 3008 ms 67160 KB Time limit exceeded
44 Halted 0 ms 0 KB -