Submission #794491

#	Time	Username	Problem	Language	Result	Execution time	Memory
794491		acatmeowmeow	Examination (JOI19_examination)	C++11	2 / 100	2195 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 subNode {
	int v = 0;
	subNode *lef = nullptr, *rig = nullptr;
	void extend() { if (!lef) lef = new subNode(), rig = new subNode(); }
	void update(int tl, int tr, int k) {
		if (tl == tr) v += 1;
		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);
		}
	}
};

struct node {
	node *lef = nullptr, *rig = nullptr;
	subNode *root2 = new subNode();
	void extend() { if (!lef) lef = new node(), rig = new node(); }
	void update(int tl, int tr, int k, int k2) {
		if (tl == tr) root2->update(0, 1e9, k2);
		else {
			extend();
			int tm = (tl + tr)/2;
			if (k <= tm) lef->update(tl, tm, k, k2);
			else rig->update(tm + 1, tr, k, k2);
			root2->update(0, 1e9, k2);
		}
	}
	int query(int tl, int tr, int l, int r, int k2) {
		if (l > r) return 0;
		else if (tl == l && tr == r) return root2->query(0, 1e9, k2, 1e9);
		else {
			extend();
			int tm = (tl + tr)/2;
			return lef->query(tl, tm, l, min(tm, r), k2) + rig->query(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];

	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];
	});

	node *root = 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]) {
			root->update(0, 1e9, S[arrIndex[arrPos]], T[arrIndex[arrPos]]);	
			arrPos++;
		}
		ans[pos] = root->query(0, 1e9, X[pos], 1e9, Y[pos]);
	}

	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