Submission #845973

#	Time	Username	Problem	Language	Result	Execution time	Memory
845973		NK_	Examination (JOI19_examination)	C++17	100 / 100	303 ms	20720 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;

struct BIT {
	int N; V<ll> data;
	void init(int _N) { N = _N; data = V<ll>(N, 0); }
	void add(int p, ll x) { for (++p;p<=N;p+=p&-p) data[p-1] += x; }
	ll sum(int l, int r) { return sum(r+1)-sum(l); }
	ll sum(int r) { ll s = 0; for(;r;r-=r&-r)s+=data[r-1]; return s; }
};

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;

	vl COOR = {INFL};
	for(int i = 0; i < N; i++) { 
		COOR.pb(A[i] + B[i]);
		COOR.pb(B[i]);
	}

	sort(begin(COOR), end(COOR));
	COOR.erase(unique(begin(COOR), end(COOR)), end(COOR));

	int M = sz(COOR);
	BIT ct, bt; ct.init(M + 1), bt.init(M + 1);
	for(int i = 0; i < N; i++) {
		int ab = lower_bound(begin(COOR), end(COOR), A[I[i]] + B[I[i]]) - begin(COOR);
		int b = lower_bound(begin(COOR), end(COOR), B[I[i]]) - begin(COOR);

		ct.add(ab, 1);
		bt.add(b, 1);

		for(auto q : QQ[i]) {
			if (q[1] == 0) {
				int x = lower_bound(begin(COOR), end(COOR), q[0]) - begin(COOR);
				ans[q[2]] += bt.sum(x, M - 1);
			} else {
				int x = lower_bound(begin(COOR), end(COOR), q[0]) - begin(COOR);
				ans[q[2]] += q[1] * ct.sum(x, M - 1);
			}
		}
	}

	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