Submission #522082

#	Time	Username	Problem	Language	Result	Execution time	Memory
522082		sidon	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	196 ms	12616 KiB

matryoshka

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

int N, Q, INF = 2e9;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> Q;
	array<int, 2> a[N], _;
	vector<array<int, 2>> qAt[N]; // post-processing

	for(auto &[r, h] : a)
		cin >> r >> h, r = -r;

	sort(a, a+N);

	int res[Q] = {};
	for(int i = 0; i < Q; ++i) {
		int A, B; cin >> A >> B;

		if(a[0][0] <= -A)
			qAt[lower_bound(a, a+N, _={-A, INF}) - a - 1].push_back({B, i});
	}

	vector<int> b;

	for(int i = 0; i < N; ++i) {
		int v = a[i][1];
		if(!i || b.back() <= v) b.push_back(v);
		else *upper_bound(begin(b), end(b), v) = v;

		for(auto &[w, qI] : qAt[i])
			res[qI] = upper_bound(begin(b), end(b), w) - begin(b);
	}

	for(int &i : res) cout << i << '\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49