Submission #1275309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275309		wedonttalkanymore	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	110 ms	8132 KiB

matryoshka

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

pair<int, int> doll[200000];
pair<pair<int, int>, int> query[200000];
int ans[200000];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> doll[i].first >> doll[i].second;
		doll[i].second = -doll[i].second;
	}
	for (int i = 0; i < q; i++) {
		cin >> query[i].first.first >> query[i].first.second;
		query[i].second = i;
	}
	sort(doll, doll + n, greater<pair<int, int>>());
	sort(query, query + q, greater<pair<pair<int, int>, int>>());

	vector<pair<int, int>> dp;
	for (int i = 0, j = 0; i < q; i++) {
		while (j < n && doll[j].first >= query[i].first.first) {
			int lds =
			    upper_bound(dp.begin(), dp.end(), make_pair(-doll[j].second, INT_MAX)) -
			    dp.begin();
			if (lds == dp.size()) dp.push_back({-doll[j].second, doll[j].first});
			else dp[lds] = {-doll[j].second, doll[j].first};
			j++;
		}
		ans[query[i].second] = upper_bound(dp.begin(), dp.end(),
		                                   make_pair(query[i].first.second, INT_MAX)) -
		                       dp.begin();
	}

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

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