oj.uz

답안 #839403

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839403 2023-08-30T01:49:07 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 345 ms 21916 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

using ii = pair<int, int>;
struct Query { int A, B, C, idx; };

const int inf = 1e9;

struct BIT{
	vector<int> tree;
	int _n;

	BIT() {}
	BIT(int N): tree(N + 1, 0), _n(N + 1) {}

	int get(int x){
		int res = 0;
		for (; x > 0; x -= x & (-x)) res += tree[x];
		return res;
	}

	void update(int x, int delta){
		for (; x < _n; x += x & (-x)) tree[x] += delta;
	}
};

struct BIT2D{
	vector<BIT> tree;
	vector<vector<int>> values;
	int _n;

	BIT2D() {}
	BIT2D(int N): tree(N + 1), values(N + 1), _n(N + 1) {}

	void prep(int row, int value){
		for (; row < _n; row += row & (-row)){
			values[row].push_back(value);
		}
	}

	void build(){
		for (int i = 0; i < _n; i++){
			sort(values[i].begin(), values[i].end());
			values[i].resize(unique(values[i].begin(), values[i].end()) - values[i].begin());
			tree[i] = BIT(values[i].size());
		}
	}

	int get(int row, int col){
		int res = 0;
		for (int R = row; R > 0; R -= R & (-R)){
			int posC = upper_bound(values[R].begin(), values[R].end(), col) - values[R].begin();
			res += tree[R].get(posC);
		}
		return res;
	}

	void update(int row, int col, int delta){
		for (int R = row; R < _n; R += R & (-R)){
			int posC = upper_bound(values[R].begin(), values[R].end(), col) - values[R].begin();
			tree[R].update(posC, delta);
		}
	}
};

int n, q;
vector<ii> students;
vector<Query> qs;

void main_program(){
	cin >> n >> q;

	students.resize(n);
	qs.resize(q);

	vector<int> xs;

	for (int i = 0; i < n; i++){
		int x, y; cin >> x >> y;
		students[i] = {inf - x, inf - y};
		xs.push_back(inf - x);
	}

	for (int i = 0; i < q; i++){
		int A, B, C; cin >> A >> B >> C;
		qs[i] = {inf - A, inf - B, inf + inf - C, i};
	}

	sort(xs.begin(), xs.end());
	xs.resize(unique(xs.begin(), xs.end()) - xs.begin());

	BIT2D bit2d(xs.size());

	for (int i = 0; i < n; i++){
		int posx = lower_bound(xs.begin(), xs.end(), students[i].first) - xs.begin();
		posx++;

		bit2d.prep(posx, students[i].second);
	}

	bit2d.build();

	sort(students.begin(), students.end(), [](ii p1, ii p2){
		return p1.first + p1.second < p2.first + p2.second;
	});
	sort(qs.begin(), qs.end(), [](Query q1, Query q2){
		return q1.C < q2.C;
	});

	vector<int> res(q);
	int it = 0;
	for (auto query: qs){
		while (it < n && students[it].first + students[it].second <= query.C){
			int posx = lower_bound(xs.begin(), xs.end(), students[it].first) - xs.begin();
			posx++;
			bit2d.update(posx, students[it].second, 1);
			it++;
		}
		int posx = upper_bound (xs.begin(), xs.end(), query.A) - xs.begin();
		res[query.idx] = bit2d.get(posx, query.B);
	}
	
	for (int i = 0; i < q; i++){
		cout << res[i] << "\n";
	}
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 6 ms 996 KB Output is correct
9 Correct 6 ms 976 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 584 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 5 ms 972 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 2 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 17552 KB Output is correct
2 Correct 280 ms 17568 KB Output is correct
3 Correct 285 ms 17564 KB Output is correct
4 Correct 140 ms 15308 KB Output is correct
5 Correct 96 ms 6388 KB Output is correct
6 Correct 50 ms 5836 KB Output is correct
7 Correct 271 ms 17556 KB Output is correct
8 Correct 261 ms 17556 KB Output is correct
9 Correct 248 ms 17604 KB Output is correct
10 Correct 58 ms 5028 KB Output is correct
11 Correct 109 ms 14968 KB Output is correct
12 Correct 32 ms 4620 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 17552 KB Output is correct
2 Correct 280 ms 17568 KB Output is correct
3 Correct 285 ms 17564 KB Output is correct
4 Correct 140 ms 15308 KB Output is correct
5 Correct 96 ms 6388 KB Output is correct
6 Correct 50 ms 5836 KB Output is correct
7 Correct 271 ms 17556 KB Output is correct
8 Correct 261 ms 17556 KB Output is correct
9 Correct 248 ms 17604 KB Output is correct
10 Correct 58 ms 5028 KB Output is correct
11 Correct 109 ms 14968 KB Output is correct
12 Correct 32 ms 4620 KB Output is correct
13 Correct 289 ms 17516 KB Output is correct
14 Correct 302 ms 17576 KB Output is correct
15 Correct 326 ms 17536 KB Output is correct
16 Correct 147 ms 15280 KB Output is correct
17 Correct 105 ms 6516 KB Output is correct
18 Correct 52 ms 5944 KB Output is correct
19 Correct 288 ms 17480 KB Output is correct
20 Correct 315 ms 17512 KB Output is correct
21 Correct 290 ms 17632 KB Output is correct
22 Correct 59 ms 4944 KB Output is correct
23 Correct 118 ms 14928 KB Output is correct
24 Correct 33 ms 4672 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 6 ms 996 KB Output is correct
9 Correct 6 ms 976 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 584 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 5 ms 972 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 284 ms 17552 KB Output is correct
20 Correct 280 ms 17568 KB Output is correct
21 Correct 285 ms 17564 KB Output is correct
22 Correct 140 ms 15308 KB Output is correct
23 Correct 96 ms 6388 KB Output is correct
24 Correct 50 ms 5836 KB Output is correct
25 Correct 271 ms 17556 KB Output is correct
26 Correct 261 ms 17556 KB Output is correct
27 Correct 248 ms 17604 KB Output is correct
28 Correct 58 ms 5028 KB Output is correct
29 Correct 109 ms 14968 KB Output is correct
30 Correct 32 ms 4620 KB Output is correct
31 Correct 289 ms 17516 KB Output is correct
32 Correct 302 ms 17576 KB Output is correct
33 Correct 326 ms 17536 KB Output is correct
34 Correct 147 ms 15280 KB Output is correct
35 Correct 105 ms 6516 KB Output is correct
36 Correct 52 ms 5944 KB Output is correct
37 Correct 288 ms 17480 KB Output is correct
38 Correct 315 ms 17512 KB Output is correct
39 Correct 290 ms 17632 KB Output is correct
40 Correct 59 ms 4944 KB Output is correct
41 Correct 118 ms 14928 KB Output is correct
42 Correct 33 ms 4672 KB Output is correct
43 Correct 342 ms 21916 KB Output is correct
44 Correct 345 ms 21760 KB Output is correct
45 Correct 326 ms 21588 KB Output is correct
46 Correct 168 ms 19316 KB Output is correct
47 Correct 110 ms 6580 KB Output is correct
48 Correct 54 ms 5728 KB Output is correct
49 Correct 318 ms 21736 KB Output is correct
50 Correct 322 ms 21556 KB Output is correct
51 Correct 291 ms 21620 KB Output is correct
52 Correct 74 ms 5216 KB Output is correct
53 Correct 124 ms 18992 KB Output is correct