5300 2023. 04. 25 17:25:54 sztomi Hadjárat cpp11 Időlimit túllépés 70/100 250ms 63736 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;
    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 = min(ert, ertek);
            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];

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});
        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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 70/100
1 Elfogadva 0/0 8ms 9404 KiB
2 Elfogadva 0/0 152ms 38928 KiB
3 Elfogadva 4/4 7ms 9904 KiB
4 Elfogadva 4/4 7ms 9732 KiB
5 Elfogadva 4/4 7ms 9988 KiB
6 Elfogadva 4/4 7ms 10200 KiB
7 Elfogadva 4/4 7ms 10188 KiB
8 Elfogadva 4/4 7ms 10284 KiB
9 Elfogadva 4/4 7ms 10288 KiB
10 Elfogadva 4/4 8ms 10288 KiB
11 Elfogadva 4/4 17ms 10356 KiB
12 Elfogadva 4/4 29ms 10356 KiB
13 Elfogadva 6/6 28ms 10612 KiB
14 Elfogadva 6/6 54ms 14952 KiB
15 Elfogadva 6/6 86ms 24948 KiB
16 Elfogadva 6/6 152ms 39824 KiB
17 Elfogadva 6/6 195ms 49484 KiB
18 Időlimit túllépés 0/6 233ms 58500 KiB
19 Időlimit túllépés 0/6 250ms 31524 KiB
20 Időlimit túllépés 0/6 244ms 63736 KiB
21 Időlimit túllépés 0/6 234ms 63456 KiB
22 Időlimit túllépés 0/6 238ms 63480 KiB