168882025-05-15 14:29:05UVinceHadjáratcpp17Elfogadva 100/100194ms1112 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxn=1e5;
int n;
int p[maxn];

struct city{
    int a,b;
    int idx;
    
    city(int x,int y,int z){
        a=x;
        b=y;
        idx=z;
    }

    bool operator<(const city &other) const {
        if (a==other.a) return b<other.b;
        return a<other.a;
    }
    bool operator>(const city &other) const {
        if (a==other.a) return b>other.b;
        return a>other.a;
    }
};

vector<set<city>> dp;

pair<int,int> get(int a, int b){
    int l=0, r=dp.size();
    int parent=0;
    while (l+1<r){
        int mid=(l+r)/2;
        bool good=false;
        auto it = dp[mid].lower_bound(city(a,b,-1));
        if (it!=dp[mid].begin()) it--;

        while (true){
            if ((*it).a<a && (*it).b<b) {
                good=true;
                break;
            }
            if (it==dp[mid].begin()) break;
            it--;
        }
        if (good) {l=mid; parent=(*it).idx;}
        else r=mid;
    }
    
    return {l, parent};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    dp.push_back({});
    dp[0].insert(city(0,0,0));
    cin>>n;
    for (int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        auto [to, par] = get(a,b);
        p[i]=par;
        to++;
        if (to==dp.size()) dp.push_back({});
        auto it = dp[to].insert(city(a,b,i)).first;
        it++;
        while (it!=dp[to].end()){
            auto it2=it;
            it++;
            if ((*it2).a>=a && (*it2).b>=b) dp[to].erase(it2);
        }
    }
    cout<<dp.size()-1<<"\n";
    int track = dp.back().begin()->idx;
    vector<int> ans;
    while (track!=0){
        ans.push_back(track);
        track=p[track];
    }
    reverse(ans.begin(), ans.end());
    for (int i : ans) cout<<i<<" ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/079ms744 KiB
3Elfogadva4/41ms320 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms500 KiB
7Elfogadva4/41ms316 KiB
8Elfogadva4/41ms316 KiB
9Elfogadva4/41ms316 KiB
10Elfogadva4/42ms316 KiB
11Elfogadva4/44ms316 KiB
12Elfogadva4/412ms532 KiB
13Elfogadva6/610ms400 KiB
14Elfogadva6/625ms508 KiB
15Elfogadva6/641ms540 KiB
16Elfogadva6/679ms768 KiB
17Elfogadva6/6103ms732 KiB
18Elfogadva6/6120ms796 KiB
19Elfogadva6/6145ms824 KiB
20Elfogadva6/6192ms1112 KiB
21Elfogadva6/6194ms1096 KiB
22Elfogadva6/6192ms1068 KiB