53052023-04-25 18:07:57sztomiHadjáratcpp11Runtime error 4/10048ms33040 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
int MAXA = 0;
//const int MAXA = (1 << 4)-1;
const int INF = 1e9+7;

struct node{
    int bal_veg=-1, jobb_veg=-1;
    pii ertek={INF,-1};
    node *bal=nullptr, *jobb=nullptr, *szulo=nullptr;
    bool bal_gyerek = false;
    node(int bal, int jobb, pii ert={INF, -1}) : bal_veg(bal), jobb_veg(jobb), ertek(ert){}
    node(){}

    pii legkisebb(int xb, int xj){
        if(xj < bal_veg || jobb_veg < xb) return {INF, -1};

        if(xb <= bal_veg && jobb_veg <= xj){
            return ertek;
        }

        pii ret = {INF, -1};
        if(bal != nullptr){
            ret = min(ret, bal->legkisebb(xb, xj));
        }
        if(jobb != nullptr){
            ret = min(ret, jobb->legkisebb(xb, xj));
        }

        return ret;
    }

    void torol_akt(){
        if(bal != nullptr) bal->torol_akt();
        if(jobb != nullptr) jobb->torol_akt();
        if(bal_gyerek){
            szulo->bal = nullptr;
        }
        else{
            szulo->jobb = nullptr;
        }
    }

    void torol(int ind){
        if(bal_veg == jobb_veg){
            torol_akt();
            return;
        }
        int mid = (bal_veg + jobb_veg) / 2;
        if(ind <= mid){
            bal->torol(ind);
        }
        else{
            jobb->torol(ind);
        }
        if(jobb == nullptr && bal == nullptr){
            torol_akt();
        }
    }

    void allit(int ind, pii ert){
        if(bal_veg == jobb_veg){
            ertek = min(ert, ertek);
            return;
        }

        int mid = (bal_veg + jobb_veg) / 2;
        if(ind <= mid){
            if(bal == nullptr){
                bal = new node(bal_veg, mid);
                bal->szulo = this;
                bal->bal_gyerek = true;
            }
            bal->allit(ind, ert);

            // a nala tuti rosszabakat torolni kene valahogy
        }
        else{
            if(jobb == nullptr){
                jobb = new node(mid+1, jobb_veg);
                jobb->szulo = this;
                jobb->bal_gyerek = true;
            }
            jobb->allit(ind, ert);
        }

        pii akt = {INF, -1};
        if(bal != nullptr){
            akt = min(akt, bal->ertek);
        }
        if(jobb != nullptr){
            akt = min(akt, jobb->ertek);
        }
        ertek = akt;
    }
};

int n;
int arany[MAXN];
int rabszolga[MAXN];
int elozo[MAXN];
node *fa[MAXN+1];
set<pii> extra_arany[MAXN+1];

void compress(){
    vector<int> van_ilyen(int(1e6+1), 0);
    for(int i = 0; i < n; i++){
        van_ilyen[arany[i]] = true;
    }
    int temp = 1;
    for(int i = 0; i <= 1e6; i++){
        if(van_ilyen[i]){
            van_ilyen[i] = temp++;
        }
    }

    MAXA = 1;
    while(MAXA < temp) MAXA *= 2;

    for(int i = 0; i < n; i++){
        arany[i] = van_ilyen[arany[i]];
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arany[i] >> rabszolga[i];
    }

    compress();

    for(int i = 0; i <= n; i++){
        fa[i] = new node(0, MAXA);
    }


    int legjobb = 0;
    int legjobb_ind = -1;

    int l, r, mid, hely;
    // {mennyi, hol}
    pii legkevesebb_szolga;
    for(int i = 0; i < n; i++){
        l = 1, r = n, hely = 0, elozo[i] = -1;
        //cout << "round: " << i << " --------------------------------------\n";
        while(l <= r){
            mid = (l+r) / 2;
            legkevesebb_szolga = fa[mid]->legkisebb(0, arany[i]-1);
            //cout << "kiprobalt mid: " << mid << " " << legkevesebb_szolga.first << " " << legkevesebb_szolga.second << "\n";
            if(legkevesebb_szolga.first < rabszolga[i]){
                hely = mid;
                elozo[i] = legkevesebb_szolga.second;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }


        //cout << "hely: " << hely << " elozo: " << elozo[i] << "\n";

        // be kell rakni a kijelolt hely utan a faba es megmondani az elozojet
        if(fa[hely+1]->legkisebb(0, arany[i]-1).first == rabszolga[i]) continue;
        fa[hely+1]->allit(arany[i], {rabszolga[i], i});
        auto it = extra_arany[hely+1].insert({arany[i], rabszolga[i]}).first;
        ++it;
        while(it != extra_arany[hely+1].end() && it->second >= rabszolga[i]){
            fa[hely+1]->torol(it->first);
            it = extra_arany[hely+1].erase(it);
        }

        if(legjobb < hely + 1){
            legjobb = hely + 1;
            legjobb_ind = i;
        }
        //cout << "-----------------------------------------------------------\n";
    }

    //cout << "legjobb: " << legjobb << "\n";
    //cout << "legjobb_ind: " << legjobb_ind << "\n";

    stack<int> mo;
    int akt = legjobb_ind;
    while(akt != -1){
        mo.push(akt + 1);

        akt = elozo[akt];
    }

    cout << legjobb << "\n";
    while(!mo.empty()){
        cout << mo.top() << " ";
        mo.pop();
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base4/100
1Accepted0/012ms19136 KiB
2Runtime error0/028ms21000 KiB
3Accepted4/49ms19560 KiB
4Runtime error0/410ms19784 KiB
5Runtime error0/410ms19964 KiB
6Runtime error0/410ms19924 KiB
7Runtime error0/49ms20244 KiB
8Runtime error0/49ms20384 KiB
9Runtime error0/410ms20432 KiB
10Runtime error0/412ms20908 KiB
11Runtime error0/413ms20992 KiB
12Runtime error0/414ms21160 KiB
13Runtime error0/613ms21384 KiB
14Runtime error0/617ms21340 KiB
15Runtime error0/619ms21856 KiB
16Runtime error0/626ms22996 KiB
17Runtime error0/628ms24140 KiB
18Runtime error0/632ms25480 KiB
19Runtime error0/637ms28240 KiB
20Runtime error0/643ms31040 KiB
21Runtime error0/648ms33040 KiB
22Runtime error0/641ms31216 KiB