Submission #379927

#	Time	Username	Problem	Language	Result	Execution time	Memory
379927		voldemort	Examination (JOI19_examination)	C++17	100 / 100	1040 ms	33140 KiB

examination

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

// Ask for sum 1 -> n for full (one based indexing)
class BIT {
	private: vector<int> tree; int n;
	int LSOne(int x) {
		return x&(-x);
	}

	public:
		void build(int x) {
			n = x;
			tree.resize(n+1);
		}
		int sum(int a) {
			int sum = 0;
			for (; a > 0; a -= LSOne(a)) sum += tree[a];
			return sum;
		}
		int sum(int a, int b) {
			return sum(b) - (a == 1 ? 0 : sum(a-1));
		}
		void update(int p, int v) {
			for (; p < n+1; p += LSOne(p)) tree[p] += v;
		}
};

int n, q, pt = 1;
vector<array<int, 4>> pts; // {s1, s2, sum, index: 1 -> contestant, else -ve query index}
vi ans;
BIT tree;
map<int, int> mp;

void solve(int l, int r) {
	if (l == r) return;
	
	int mid = (l+r)/2;
	
	vector<array<int, 3>> curr; // {s2, sum, index: 1 -> contestant, else -ve query index}
	for_(i, mid+1, r+1) if (pts[i][3] != 1) curr.push_back({pts[i][1], pts[i][2], pts[i][3]});
	for_(i, l, mid+1) if (pts[i][3] == 1) curr.push_back({pts[i][1], pts[i][2], 1});
	
	sort(curr.rbegin(), curr.rend());
	
	for (auto &i: curr) {
		if (i[2] == 1) tree.update(i[1], 1);
		else ans[-i[2]] += tree.sum(i[1], pt);
	}
	
	for (auto &i: curr) if (i[2] == 1) tree.update(i[1], -1);
	
	solve(l, mid); solve(mid+1, r);
}



int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q;
	pts.resize(n+q); ans.resize(q);
	
	for_(i, 0, n) {
		cin >> pts[i][0] >> pts[i][1];
		pts[i][2] = pts[i][0]+pts[i][1]; pts[i][3] = 1;
		mp[pts[i][1]] = mp[pts[i][2]] = 0;
	}
	for_(i, n, n+q) {
		cin >> pts[i][0] >> pts[i][1] >> pts[i][2];
		pts[i][3] = n-i;
		mp[pts[i][1]] = mp[pts[i][2]] = 0;
	}
	
	for (auto &i: mp) mp[i.first] = pt++;
	for_(i, 0, n+q) {
		pts[i][1] = mp[pts[i][1]]; pts[i][2] = mp[pts[i][2]]; 
	}
	
	sort(pts.rbegin(), pts.rend());
	tree.build(pt);
	solve(0, n+q-1);
	
	for (auto i: ans) cout << i << endl;
	cout << endl;
}

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