#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef CB
freopen("be2.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
int N;
cin>>N;
vector<int>r(N+1),a(N+1),p(N,-1);
for(int i=0;i<N;i++){
cin>>r[i]>>a[i];
}
vector<multimap<int,int>>v(N+1);
v[0].emplace(0,N);
for(int i=0;i<N;i++){
int l=0,h=i+1;
while(l!=h){
int m=(l+h)/2;
auto it=v[m].lower_bound(r[i]);
if(it==v[m].begin()){
h=m;
continue;
}
it--;
if(a[it->second]>=a[i]){
h=m;
continue;
}
p[i]=it->second;
l=m+1;
}
auto it=v[l].emplace(r[i],i);
if(it!=v[l].begin()&&a[it->second]>=a[prev(it)->second]){
v[l].erase(it);
continue;
}
it++;
while(it!=v[l].end()&&a[it->second]>=a[i]){
it=v[l].erase(it);
}
}
int ans=N;
while(v[ans].empty())ans--;
cout<<ans<<'\n';
vector<int>anss;
for(int i=v[ans].begin()->second;i!=N;i=p[i])anss.push_back(i);
reverse(anss.begin(),anss.end());
for(int i:anss)cout<<i+1<<' ';cout<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 48ms | 8160 KiB | |||
3 | Elfogadva | 4/4 | 3ms | 2348 KiB | |||
4 | Elfogadva | 4/4 | 3ms | 2320 KiB | |||
5 | Elfogadva | 4/4 | 3ms | 2340 KiB | |||
6 | Elfogadva | 4/4 | 3ms | 2540 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 2780 KiB | |||
8 | Elfogadva | 4/4 | 3ms | 2836 KiB | |||
9 | Elfogadva | 4/4 | 3ms | 2852 KiB | |||
10 | Elfogadva | 4/4 | 3ms | 3176 KiB | |||
11 | Elfogadva | 4/4 | 6ms | 3408 KiB | |||
12 | Elfogadva | 4/4 | 9ms | 4404 KiB | |||
13 | Elfogadva | 6/6 | 9ms | 4492 KiB | |||
14 | Elfogadva | 6/6 | 18ms | 5788 KiB | |||
15 | Elfogadva | 6/6 | 28ms | 6904 KiB | |||
16 | Elfogadva | 6/6 | 48ms | 9500 KiB | |||
17 | Elfogadva | 6/6 | 59ms | 10868 KiB | |||
18 | Elfogadva | 6/6 | 70ms | 12188 KiB | |||
19 | Elfogadva | 6/6 | 82ms | 13352 KiB | |||
20 | Elfogadva | 6/6 | 104ms | 15880 KiB | |||
21 | Elfogadva | 6/6 | 104ms | 15752 KiB | |||
22 | Elfogadva | 6/6 | 104ms | 15572 KiB |