Submission #1259880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259880		ssitaram	Examination (JOI19_examination)	C++20	100 / 100	222 ms	31772 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

template<typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q; cin >> n >> q;
	vector<pair<int, int>> st(n);
	for (pair<int, int>& i : st) cin >> i.first >> i.second;
	sort(st.begin(), st.end());
	vector<int> ans(q);
	vector<vector<int>> attB(n);
	vector<vector<vector<int>>> attZ(n);
	auto atZ = [&](int v, int qn, int mul = 1) -> void {
		auto it = lower_bound(st.begin(), st.end(), make_pair(v + 1, 0));
		if (it != st.begin()) {
			attZ[it - st.begin() - 1].push_back({qn, mul});
		}
	};
	auto atB = [&](int v, int qn) -> void {
		auto it = lower_bound(st.begin(), st.end(), make_pair(v, 0));
		if (it != st.end()) {
			attB[it - st.begin()].push_back(qn);
		}
	};
	vector<vector<int>> qs(q);
	for (int i = 0; i < q; ++i) {
		int x, y, z; cin >> x >> y >> z;
		qs[i] = {x, y, z};
		int lim = z - y;
		if (lim <= x) {
			atB(x, i);
		} else {
			atB(lim, i);
			atZ(lim - 1, i);
			atZ(x - 1, i, -1);
		}
	}
	indexed_set<pair<int, int>> cur;
	for (int i = 0; i < n; ++i) {
		cur.insert({-(st[i].first + st[i].second), i});
		for (vector<int>& j : attZ[i]) {
			int count = cur.order_of_key({-qs[j[0]][2], INT32_MAX});
			ans[j[0]] += j[1] * count;
		}
	}
	cur.clear();
	for (int i = n - 1; i >= 0; --i) {
		cur.insert({-st[i].second, i});
		for (int& j : attB[i]) {
			int count = cur.order_of_key({-qs[j][1], INT32_MAX});
			ans[j] += count;
		}
	}
	for (int& i : ans) {
		cout << i << '\n';
	}
	return 0;
}

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