52942023-04-25 16:25:37sztomiHadjáratcpp11Wrong answer 60/100178ms62036 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXA = (1 << 20)-1;
//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;
    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 allit(int ind, pii ert){
        if(bal_veg == jobb_veg){
            ertek = ert;
            return;
        }

        int mid = (bal_veg + jobb_veg) / 2;
        if(ind <= mid){
            if(bal == nullptr){
                bal = new node(bal_veg, mid);
            }
            bal->allit(ind, ert);
        }
        else{
            if(jobb == nullptr){
                jobb = new node(mid+1, jobb_veg);
            }
            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];


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

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arany[i] >> rabszolga[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(1, 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
        fa[hely+1]->allit(arany[i], {rabszolga[i], i});
        if(legjobb < hely + 1){
            legjobb = hely + 1;
            legjobb_ind = i;
        }
        //cout << "-----------------------------------------------------------\n";
    }

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

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

        akt = elozo[akt];
    }

    cout << legjobb << "\n";
    for(int i = mo.size()-1; i >= 0; i--){
        cout << mo[i] << " ";
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base60/100
1Accepted0/03ms1860 KiB
2Accepted0/0165ms45688 KiB
3Accepted4/43ms2992 KiB
4Accepted4/43ms3080 KiB
5Accepted4/43ms3312 KiB
6Accepted4/43ms3528 KiB
7Accepted4/43ms3748 KiB
8Wrong answer0/43ms3964 KiB
9Accepted4/43ms4216 KiB
10Accepted4/44ms5300 KiB
11Accepted4/416ms10020 KiB
12Accepted4/430ms15056 KiB
13Accepted6/628ms12336 KiB
14Accepted6/659ms18128 KiB
15Accepted6/693ms33192 KiB
16Accepted6/6165ms49696 KiB
17Runtime error0/6178ms62036 KiB
18Runtime error0/6166ms62016 KiB
19Runtime error0/6171ms61772 KiB
20Runtime error0/6160ms61712 KiB
21Runtime error0/6165ms61704 KiB
22Runtime error0/6165ms61624 KiB