#include <bits/stdc++.h>
using namespace std;
const int c=100005;
struct st{
int a,b,id;
st(int aa, int bb, int i){
a=aa; b=bb; id=i;
}
st(){a=b=id=0;}
bool operator<(const st& o) const {
return a<o.a || (a==o.a && b<o.b);
}
};
int n;
int len=0;
set<st> s[c];
int prv[c];
vector<int> ans;
int query(int idx, st& k){
if(idx==0) return 0;
auto it=s[idx].lower_bound(st(k.a,0,0));
if(it==s[idx].begin()) return -1;
--it;
if(it->b < k.b) return it->id;
return -1;
}
void ins(int idx, st& k){
auto it=s[idx].lower_bound(k);
if(it != s[idx].begin()){
auto it2=it; it2--;
if(it2->a <= k.a && it2->b <= k.b) return;
}
it=s[idx].insert(it,k);
it++;
while(it != s[idx].end() && it->b >= k.b){
it=s[idx].erase(it);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int a,b; cin>>a>>b;
st cur=st(a,b,i);
int l,r; l=0; r=len;
int res=0,id=0;
while(l<=r){
int mid=l+r>>1;
int iid=query(mid,cur);
if(iid != -1){
res=mid; l=mid+1;
id=iid;
}
else r=mid-1;
}
prv[i]=id;
++res;
if(res>len){
++len; s[len].insert(cur);
}
else{
ins(res,cur);
}
}
cout << len << '\n';
int cur=s[len].begin()->id;
while(cur != 0){
ans.emplace_back(cur); cur=prv[cur];
}
for(int i=ans.size()-1;i>=0;i--){
cout << ans[i] << ' ';
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 7ms | 11272 KiB | |||
2 | Elfogadva | 0/0 | 48ms | 12636 KiB | |||
3 | Elfogadva | 4/4 | 6ms | 11812 KiB | |||
4 | Elfogadva | 4/4 | 6ms | 11808 KiB | |||
5 | Elfogadva | 4/4 | 4ms | 11816 KiB | |||
6 | Elfogadva | 4/4 | 4ms | 11816 KiB | |||
7 | Elfogadva | 4/4 | 4ms | 11820 KiB | |||
8 | Elfogadva | 4/4 | 4ms | 11824 KiB | |||
9 | Elfogadva | 4/4 | 4ms | 11832 KiB | |||
10 | Elfogadva | 4/4 | 6ms | 11980 KiB | |||
11 | Elfogadva | 4/4 | 8ms | 12036 KiB | |||
12 | Elfogadva | 4/4 | 12ms | 12268 KiB | |||
13 | Elfogadva | 6/6 | 12ms | 12384 KiB | |||
14 | Elfogadva | 6/6 | 19ms | 12672 KiB | |||
15 | Elfogadva | 6/6 | 28ms | 13204 KiB | |||
16 | Elfogadva | 6/6 | 48ms | 14064 KiB | |||
17 | Elfogadva | 6/6 | 57ms | 14964 KiB | |||
18 | Elfogadva | 6/6 | 65ms | 16100 KiB | |||
19 | Elfogadva | 6/6 | 79ms | 17224 KiB | |||
20 | Elfogadva | 6/6 | 97ms | 18832 KiB | |||
21 | Elfogadva | 6/6 | 92ms | 20316 KiB | |||
22 | Elfogadva | 6/6 | 86ms | 21524 KiB |