Submission #1214565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214565		dubabuba	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	219 ms	7276 KiB

matryoshka

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

struct QUERY {
	int a, b;
	int index;

	QUERY() : index(0), a(0), b(0) {};
	QUERY(int i, int a, int b) : index(i), a(a), b(b) {}
};

const int INF = 2e9 + 10;
const int mxn = 2e5 + 10;
int n, q, ans[mxn];
QUERY query[mxn];
pii doll[mxn];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> q;
	for(int i = 0; i < n; i++)
		cin >> doll[i].ff >> doll[i].ss;

	sort(doll, doll + n, [&](pii a, pii b) {
		if(a.ff != b.ff) return a.ff < b.ff;
		return a.ss > b.ss;
	});
	reverse(doll, doll + n);

	for(int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		query[i] = QUERY(i, a, b);
	}

	sort(query, query + q, [&](auto x, auto y) { return x.a > y.a; });

	vector<int> MS(n + 1, INF);
	function<void(int)> add = [&](int i) {
		int val = doll[i].ss;
		int id = upper_bound(MS.begin(), MS.end(), val) - MS.begin();
		MS[id] = val;
	};

	int ptr = 0;
	for(int i = 0; i < q; i++) {
		int a = query[i].a;
		int b = query[i].b;
		int id = query[i].index;

		while(ptr < n && doll[ptr].ff >= a) {
			add(ptr);
			ptr++;
		}

		int len = upper_bound(MS.begin(), MS.end(), b) - MS.begin();
		ans[id] = len;
	}

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

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