Submission #1305896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305896		vlomaczk	Examination (JOI19_examination)	C++20	0 / 100	130 ms	16600 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>;

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;
	}
	ordered_set<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);
		}
	}
	ordered_set<ll> os2;
	for(auto[s,i] : sweep) {
		if(i > 0) {
			--i;
			os2.insert(pkt[i].y);
		} else {
			i*=-1;
			ans[i] -= os2.order_of_key(Q[i].B);
		}
	}
	for(ll i=0; i<q; ++i) cout << ans[i] << "\n";

	return 0;
}

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