제출 #1305901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305901		vlomaczk	Examination (JOI19_examination)	C++20	100 / 100	167 ms	15092 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename TY>
struct MultiOrderedSet {
	ordered_set<pair<TY, int>> os;
	int cnt = 0;
	void insert(TY x) {
		os.insert({x, cnt++});
	}
	void erase(TY x) {
		int idx = os.order_of_key({x,-1});
		assert(idx < os.size());
		os.erase(*os.find_by_order(idx));
	}
	TY first() { return os.begin()->first; }
	TY last() { return os.rbegin()->first; }
	void clear() {
		while(os.size()) os.erase(*os.begin());
	}
	int size() { return os.size(); }
	bool empty() { return os.empty(); }
	int order_of_key(TY x) {
		return os.order_of_key({x, -1});
	}
	TY find_by_order(ll x) {
		return os.find_by_order(x)->first;
	}
};

struct Poll {
	ll x, y;	
};

struct Query {
	ll A,B,C;
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n,q;
	cin >> n >> q;
	vector<Poll> pkt(n);
	for(ll i=0; i<n; ++i) cin >> pkt[i].x >> pkt[i].y;
	vector<Query> Q(q);
	for(ll i=0; i<q; ++i) {
		cin >> Q[i].A >> Q[i].B >> Q[i].C;
		Q[i].C = max(Q[i].C, Q[i].A + Q[i].B);
	}
	vector<ll> ans(q);
	ll ile = 0;
	vector<pair<ll, ll>> sweep;
	for(ll i=0; i<n; ++i) sweep.push_back({pkt[i].x + pkt[i].y, i+1});
	for(ll i=0; i<q; ++i) sweep.push_back({Q[i].C, -i});
	sort(sweep.begin(), sweep.end());
	reverse(sweep.begin(), sweep.end());
	for(auto[s,i] : sweep) {
		if(i > 0) {
			ile++;
		} else ans[-i] = ile;
	}
	MultiOrderedSet<ll> os;
	for(auto[s,i] : sweep) {
		if(i > 0) {
			--i;
			os.insert(pkt[i].x);
		} else {
			i*=-1;
			ans[i] -= os.order_of_key(Q[i].A);
		}
	}
	os.clear();
	for(auto[s,i] : sweep) {
		if(i > 0) {
			--i;
			os.insert(pkt[i].y);
		} else {
			i*=-1;
			ans[i] -= os.order_of_key(Q[i].B);
		}
	}
	for(ll i=0; i<q; ++i) cout << ans[i] << "\n";

	return 0;
}

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