Submission #1312693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312693		crispxx	Examination (JOI19_examination)	C++20	20 / 100	210 ms	24100 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using ll = long long;

using ordered_set = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;

void solve() {
	int n, q; cin >> n >> q;
	
	vector<int> s(n), t(n);
	
	vector<int> cmp;
	
	for(int i = 0; i < n; i++) {
		cin >> s[i] >> t[i];
		
		cmp.push_back(s[i]);
		cmp.push_back(t[i]);
	}
	
	vector<array<int, 4>> qrs(q);
	
	for(int i = 0; i < q; i++) {
		auto &[x, y, z, ind] = qrs[i];
		
		cin >> x >> y >> z;
		
		ind = i;
		
		cmp.push_back(x);
		cmp.push_back(y);
		cmp.push_back(z);
	}
	
	sort(cmp.begin(), cmp.end());
	
	auto idx = [&](int x) {
		return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
	};
	
	int m = cmp.size();
	
	vector<vector<int>> what(m);
	
	for(int i = 0; i < n; i++) {
		what[idx(s[i])].push_back(idx(t[i]));
	}
	
	sort(qrs.begin(), qrs.end(), greater<>());
	
	ordered_set st;
	
	vector<int> ans(q);
	
	for(int i = 0, j = m - 1; i < q; i++) {
		auto &[x, y, z, ind] = qrs[i];
		
		x = idx(x);
		y = idx(y);
		z = idx(z);
		
		while(j >= x) {
			for(auto T : what[j]) {
				st.insert(T);
			}
			j--;
		}
		
		ans[ind] = st.size() - st.order_of_key(y);
	}
	
	for(auto &x : ans) cout << x << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

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