제출 #839403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839403		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	345 ms	21916 KiB

examination

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