1355 | 2022. 05. 22 13:48:23 | Szin Attila | Hadjárat | cpp14 | Elfogadva 100/100 | 97ms | 21416 KiB |
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;
const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
struct city {
int a,b,ind;
bool operator<(const city& temp) const {
return a < temp.a;
}
};
int n, mo, moind;
vector<set<city>> v;
vector<int> p;
stack <int> ki; //NEM VAGYOK ERETNEK
int main() {
#pragma region
#ifndef ONLINE_JUDGE
freopen("../input.txt", "r", stdin);
freopen("../output.txt", "w", stdout);
#endif
InTheNameOfGod;
#pragma endregion
cin >> n;
v.resize(n+2);
p.resize(n+2, -1);
v[0].insert({0, 0, 0});
for(int i = 1; i <= n; i++) {
int a,b;
cin >> a >> b;
city cur = {a, b, i};
int l = 0, r = mo, veg = 0, id = -1;
while(l <= r) {
int mid = (l + r) / 2, temp = -1;
auto it = v[mid].lower_bound(cur);
if(it != v[mid].begin() && (--it) -> b < b) temp = it -> ind;
/*cout << "lower_bound: " << it -> ind << endl;
cout << mid << ": " << temp << endl;*/
if(temp != -1) {
veg = mid;
l = mid+1;
id = temp;
}
else {
r = mid-1;
}
}
//cout << i << ": " << veg << endl;
p[i] = id;
veg++;
if(veg > mo) {
mo = veg;
moind = i;
}
auto it = v[veg].lower_bound(cur);
while (it != v[veg].end() && it -> b >= b) {
it = v[veg].erase(it);
}
if(it == v[veg].end() || it->a > a) v[veg].insert(cur);
}
cout << mo << "\n";
int cur = moind;
while(cur != 0) {
ki.push(cur);
cur = p[cur];
}
while(!ki.empty()) {
cout << ki.top() << ' ';
ki.pop();
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1772 KiB | |||
2 | Elfogadva | 0/0 | 41ms | 7824 KiB | |||
3 | Elfogadva | 4/4 | 1ms | 2440 KiB | |||
4 | Elfogadva | 4/4 | 1ms | 2448 KiB | |||
5 | Elfogadva | 4/4 | 1ms | 2448 KiB | |||
6 | Elfogadva | 4/4 | 1ms | 2456 KiB | |||
7 | Elfogadva | 4/4 | 1ms | 2460 KiB | |||
8 | Elfogadva | 4/4 | 2ms | 2468 KiB | |||
9 | Elfogadva | 4/4 | 2ms | 2484 KiB | |||
10 | Elfogadva | 4/4 | 2ms | 2540 KiB | |||
11 | Elfogadva | 4/4 | 4ms | 2936 KiB | |||
12 | Elfogadva | 4/4 | 8ms | 3500 KiB | |||
13 | Elfogadva | 6/6 | 8ms | 3620 KiB | |||
14 | Elfogadva | 6/6 | 16ms | 4888 KiB | |||
15 | Elfogadva | 6/6 | 24ms | 6240 KiB | |||
16 | Elfogadva | 6/6 | 43ms | 9320 KiB | |||
17 | Elfogadva | 6/6 | 56ms | 11200 KiB | |||
18 | Elfogadva | 6/6 | 78ms | 13172 KiB | |||
19 | Elfogadva | 6/6 | 71ms | 15288 KiB | |||
20 | Elfogadva | 6/6 | 93ms | 18708 KiB | |||
21 | Elfogadva | 6/6 | 97ms | 20192 KiB | |||
22 | Elfogadva | 6/6 | 97ms | 21416 KiB |