Submission #845963

#	Time	Username	Problem	Language	Result	Execution time	Memory
845963		NK_	Examination (JOI19_examination)	C++17	100 / 100	411 ms	29492 KiB

examination

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, Q; cin >> N >> Q;

	vl A(N), B(N); for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
	}

	vi I(N); iota(begin(I), end(I), 0);

	sort(begin(I), end(I), [&](int a, int b) {
		return A[a] > A[b];
	}); 

	V<V<array<ll, 3>>> QQ(N); vi ans(Q);

	auto find = [&](ll x) {
		int lo = -1, hi = N - 1;
		while(lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (x <= A[I[mid]]) lo = mid;
			else hi = mid - 1;
		}
		return lo;
	};

	for(int i = 0; i < Q; i++) {
		ll a, b, c; cin >> a >> b >> c; 
		// cout << a << " " << b << " " << c << endl;

		// c-query
		int cq = find(a);
		if (cq != -1) {
			QQ[cq].pb({c, 1, i});
			// cout << i << " " << cq << endl;
		}

		// everything after is a b-query
		int bq = min(find(c - b), cq);
		if (bq != -1) {
			QQ[bq].pb({c, -1, i});
			QQ[bq].pb({b, 0, i});
			// cout << i << " " << bq << endl;
		}
	}

	// cout << endl;

	iset<pl> ct, bt; 

	for(int i = 0; i < N; i++) { 
		ct.insert(mp(A[I[i]] + B[I[i]], i));
		bt.insert(mp(B[I[i]], i));

		// cout << i << endl;
		for(auto q : QQ[i]) {
			if (q[1] == 0) {
				ans[q[2]] += int(sz(bt) - bt.order_of_key(mp(q[0], -MOD)));
				// cout << q[2] << " " << q[1] << " " << int(sz(bt) - bt.order_of_key(mp(q[0], -MOD))) << endl;
			} else {
				ans[q[2]] += q[1] * int(sz(ct) - ct.order_of_key(mp(q[0], -MOD)));
				// cout << "> " << sz(ct) << " " << ct.order_of_key(mp(q[0], -MOD)) << endl;
				// cout << q[2] << " " << q[1] << " " << q[1] * int(sz(ct) - ct.order_of_key(mp(q[0], -MOD))) << endl;
			}
		}
		// cout << endl;
	}

	for(int i = 0; i < Q; i++) cout << ans[i] << endl;

	exit(0-0);
} 			

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