Submission #794589

#	Time	Username	Problem	Language	Result	Execution time	Memory
794589		acatmeowmeow	Examination (JOI19_examination)	C++11	2 / 100	1809 ms	1048576 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
int n, q, S[N + 5], T[N + 5], X[N + 5], Y[N + 5], Z[N + 5], queryIndex[N + 5], arrIndex[N + 5], ans[N + 5];

struct node {
	int v;
	node *lef = nullptr, *rig = nullptr;
	void extend() { if (!lef) lef = new node(), rig = new node(); }
	void update(int tl, int tr, int k) {
		if (tl == tr) v++;
		else {
			extend();
			int tm = (tl + tr)/2;
			if (k <= tm) lef->update(tl, tm, k);
			else rig->update(tm + 1, tr, k);
			v = lef->v + rig->v;
		}
	}
	int query(int tl, int tr, int l, int r) {
		if (l > r) return 0;
		else if (tl == l && tr == r) return v;
		else {
			extend();
			int tm = (tl + tr)/2;
			return lef->query(tl, tm, l, min(tm, r)) + rig->query(tm + 1, tr, max(l, tm + 1), r);
		}
	}
} *tree[8*N + 5];

void update(int v, int tl, int tr, int k, int k2) {
	if (tl == tr) tree[v]->update(0, 2*N, k2);
	else {
		int tm = (tl + tr)/2;
		if (k <= tm) update(v*2, tl, tm, k, k2);
		else update(v*2 + 1, tm + 1, tr, k, k2);
		tree[v]->update(0, 2*N, k2);
	}
}

int query(int v, int tl, int tr, int l, int r, int k2) {
	if (l > r) return 0;
	else if (tl == l && tr == r) return tree[v]->query(0, 2*N, k2, 2*N);
	else {
		int tm = (tl + tr)/2;
		return query(v*2, tl, tm, l, min(tm, r), k2) + query(v*2 + 1, tm + 1, tr, max(l, tm + 1), r, k2);
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> S[i] >> T[i];
	for (int i = 1; i <= q; i++) cin >> X[i] >> Y[i] >> Z[i];
	
	vector<int> mp1, mp2;
	for (int i = 1; i <= n; i++) mp1.push_back(S[i]), mp2.push_back(T[i]);
	for (int i = 1; i <= q; i++) mp1.push_back(X[i]), mp2.push_back(Y[i]);
	sort(mp1.begin(), mp1.end());
	sort(mp2.begin(), mp2.end());
	mp1.erase(unique(mp1.begin(), mp1.end()), mp1.end());
	mp2.erase(unique(mp2.begin(), mp2.end()), mp2.end());
	auto find = [&](int v, vector<int>&mp) { return lower_bound(mp.begin(), mp.end(), v) - mp.begin(); };

	iota(queryIndex + 1, queryIndex + q + 1, 1);
	sort(queryIndex + 1, queryIndex + q + 1, [&](int a, int b){
			if (Z[a] == Z[b]) return pair<int, int>(X[a], Y[a]) > pair<int, int>(X[b], Y[b]);
			else return Z[a] > Z[b];
	});

	iota(arrIndex + 1, arrIndex + n + 1, 1);
	sort(arrIndex + 1, arrIndex + n + 1, [&](int a, int b) {
			if (S[a] + T[a] == S[b] + T[b]) return pair<int, int>(S[a], T[a]) > pair<int, int>(S[b], T[b]);
			else return S[a] + T[a] > S[b] + T[b];
	});

	for (int i = 1; i <= 8*N; i++) tree[i] = new node();

	for (int i = 1, arrPos = 1; i <= q; i++) {
		int pos = queryIndex[i];
		while (arrPos <= n && S[arrIndex[arrPos]] + T[arrIndex[arrPos]] >= Z[pos]) {
			int mpS = find(S[arrIndex[arrPos]], mp1), mpT = find(T[arrIndex[arrPos]], mp2);
			update(1, 0, 2*N, mpS, mpT);
			arrPos++;
		}
		int mpX = find(X[pos], mp1), mpY = find(Y[pos], mp2);
		ans[pos] = query(1, 0, 2*N, mpX, 2*N, mpY);
	}

	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
	return 0;
}

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