114392024-09-24 18:50:11HoraHadjáratcpp14Hibás válasz 96/100166ms2432 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <array>

using namespace std;

vector<set<array<int, 3>>> lis;

int query(array<int, 3> q) { //mire helyezheto ra
	int lo = 0, hi = lis.size();
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		auto it = lis[mid].upper_bound({ q[0], -1, -1 });
		if (it == lis[mid].begin()) hi = mid;
		else {
			it--;
			if ((*it)[1] < q[1])	lo = mid;
			else hi = mid;
		}
	}
	return lo;
}

int ind(array<int, 3> q, int mid) {
	auto it = lis[mid].upper_bound({ q[0], -1, -1 });
	it--;
	return (*it)[2];
}

void add(array<int, 3> q, int x) {
	lis[x].insert(q);
	auto it = lis[x].upper_bound(q);
	while (it != lis[x].end()) {
		if ((*it)[1] >= q[1]) it = lis[x].erase(it);
		else break;
	}
}

int main() {
	int n;
	cin >> n;
	lis = { {{0, 0, 0}} };
	vector<int> p(n + 1); //for backtrack
	p[0] = 0;
	array<int, 3> a;
	for (int i = 1; i <= n; i++) {
		a[2] = i;
		cin >> a[0] >> a[1];
		int x = query(a);
		if (x == lis.size() - 1) {
			lis.push_back({ a });
		}
		else add(a, x + 1);
		p[i] = ind(a, x);
	}
	vector<int> ans;
	int c = (*lis.back().begin())[2];
	while (c != 0) {
		ans.push_back(c);
		c = p[c];
	}
	cout << lis.size() - 1 << "\n";
	reverse(ans.begin(), ans.end());
	for (auto x : ans) cout << x << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base96/100
1Elfogadva0/03ms504 KiB
2Elfogadva0/076ms1376 KiB
3Elfogadva4/43ms528 KiB
4Elfogadva4/43ms504 KiB
5Elfogadva4/43ms420 KiB
6Elfogadva4/43ms504 KiB
7Elfogadva4/42ms376 KiB
8Hibás válasz0/43ms504 KiB
9Elfogadva4/43ms376 KiB
10Elfogadva4/44ms376 KiB
11Elfogadva4/48ms376 KiB
12Elfogadva4/416ms748 KiB
13Elfogadva6/614ms616 KiB
14Elfogadva6/628ms892 KiB
15Elfogadva6/645ms952 KiB
16Elfogadva6/676ms1440 KiB
17Elfogadva6/697ms1640 KiB
18Elfogadva6/6114ms1704 KiB
19Elfogadva6/6130ms1996 KiB
20Elfogadva6/6166ms2408 KiB
21Elfogadva6/6166ms2408 KiB
22Elfogadva6/6165ms2432 KiB