5306 2023. 04. 25 18:09:14 sztomi Hadjárat cpp11 Futási hiba 4/100 48ms 32420 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(szulo != nullptr){
            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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 4/100
1 Elfogadva 0/0 9ms 19136 KiB
2 Futási hiba 0/0 28ms 21096 KiB
3 Elfogadva 4/4 10ms 19656 KiB
4 Futási hiba 0/4 10ms 19588 KiB
5 Futási hiba 0/4 10ms 19652 KiB
6 Futási hiba 0/4 10ms 19904 KiB
7 Futási hiba 0/4 10ms 19804 KiB
8 Futási hiba 0/4 10ms 19964 KiB
9 Futási hiba 0/4 9ms 20336 KiB
10 Futási hiba 0/4 12ms 20420 KiB
11 Futási hiba 0/4 10ms 20628 KiB
12 Futási hiba 0/4 14ms 20760 KiB
13 Futási hiba 0/6 14ms 20748 KiB
14 Futási hiba 0/6 17ms 20696 KiB
15 Futási hiba 0/6 19ms 21088 KiB
16 Futási hiba 0/6 28ms 22124 KiB
17 Futási hiba 0/6 29ms 23180 KiB
18 Futási hiba 0/6 30ms 24784 KiB
19 Futási hiba 0/6 35ms 27748 KiB
20 Futási hiba 0/6 43ms 30372 KiB
21 Futási hiba 0/6 48ms 32420 KiB
22 Futási hiba 0/6 43ms 30688 KiB