#include <bits/stdc++.h>
using namespace std;
const int N = (1<<18);
struct point{
int x, y, id;
bool operator<(const point& o) const{
return x < o.x;
}
};
int n, p[N];
set<point> last[N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
last[0].insert({0,0,0});
int totmx=0, mxpos;
for(int i = 1; i <= n; ++i){
int x, y, mx=0; cin >> x >> y;
for(int j = 17; j >= 0; --j){
int nmx = mx + (1<<j);
auto it = last[nmx].lower_bound({x,y,-1});
if(it != last[nmx].begin()){
--it;
if(it->y >= y) continue;
mx = nmx;
p[i] = it->id;
}
}
++mx;
auto it = last[mx].lower_bound({x,y,-1});
while(it != last[mx].end() && it->y >= y) it = last[mx].erase(it);
if(it == last[mx].end() || it->x != x) last[mx].insert({x,y,i});
if(mx > totmx){
totmx = mx;
mxpos = i;
}
}
cout << totmx << '\n';
vector<int> res;
while(mxpos){
res.push_back(mxpos);
mxpos = p[mxpos];
}
for(int i = res.size()-1; i >=0; --i) cout <<res[i] << ' ';
cout << '\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 16ms | 26400 KiB | |||
2 | Elfogadva | 0/0 | 56ms | 27796 KiB | |||
3 | Elfogadva | 4/4 | 13ms | 27020 KiB | |||
4 | Elfogadva | 4/4 | 12ms | 27020 KiB | |||
5 | Elfogadva | 4/4 | 13ms | 27028 KiB | |||
6 | Elfogadva | 4/4 | 13ms | 27076 KiB | |||
7 | Elfogadva | 4/4 | 13ms | 27024 KiB | |||
8 | Elfogadva | 4/4 | 13ms | 27040 KiB | |||
9 | Elfogadva | 4/4 | 14ms | 27044 KiB | |||
10 | Elfogadva | 4/4 | 17ms | 27068 KiB | |||
11 | Elfogadva | 4/4 | 17ms | 27260 KiB | |||
12 | Elfogadva | 4/4 | 19ms | 27492 KiB | |||
13 | Elfogadva | 6/6 | 19ms | 27604 KiB | |||
14 | Elfogadva | 6/6 | 28ms | 27896 KiB | |||
15 | Elfogadva | 6/6 | 37ms | 28424 KiB | |||
16 | Elfogadva | 6/6 | 52ms | 29156 KiB | |||
17 | Elfogadva | 6/6 | 65ms | 30180 KiB | |||
18 | Elfogadva | 6/6 | 75ms | 31232 KiB | |||
19 | Elfogadva | 6/6 | 82ms | 32444 KiB | |||
20 | Elfogadva | 6/6 | 108ms | 34056 KiB | |||
21 | Elfogadva | 6/6 | 104ms | 35440 KiB | |||
22 | Elfogadva | 6/6 | 104ms | 36776 KiB |