1195 2022. 03. 15 20:03:54 k_balint Hadjárat cpp14 Elfogadva 100/100 97ms 21524 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 Ö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