11952022-03-15 20:03:54k_balintHadjáratcpp14Elfogadva 100/10097ms21524 KiB
#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ÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/07ms11272 KiB
2Elfogadva0/048ms12636 KiB
3Elfogadva4/46ms11812 KiB
4Elfogadva4/46ms11808 KiB
5Elfogadva4/44ms11816 KiB
6Elfogadva4/44ms11816 KiB
7Elfogadva4/44ms11820 KiB
8Elfogadva4/44ms11824 KiB
9Elfogadva4/44ms11832 KiB
10Elfogadva4/46ms11980 KiB
11Elfogadva4/48ms12036 KiB
12Elfogadva4/412ms12268 KiB
13Elfogadva6/612ms12384 KiB
14Elfogadva6/619ms12672 KiB
15Elfogadva6/628ms13204 KiB
16Elfogadva6/648ms14064 KiB
17Elfogadva6/657ms14964 KiB
18Elfogadva6/665ms16100 KiB
19Elfogadva6/679ms17224 KiB
20Elfogadva6/697ms18832 KiB
21Elfogadva6/692ms20316 KiB
22Elfogadva6/686ms21524 KiB