52972023-04-25 17:04:45sztomiHadjáratcpp11Hibás válasz 60/100180ms63096 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 = 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];

void compress(){
    int *van_ilyen1 = new int[int(1e6+1)]{0};
    int *van_ilyen2 = new int [int(1e6+1)]{0};
    for(int i = 0; i < n; i++){
        van_ilyen1[arany[i]] = true;
        van_ilyen2[rabszolga[i]] = true;
    }
    int temp1 = 1;
    int temp2 = 1;
    for(int i = 0; i <= 1e6; i++){
        if(van_ilyen1[i]){
            van_ilyen1[i] = temp1++;
        }
        if(van_ilyen2[i]){
            van_ilyen2[i] = temp2++;
        }
    }

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

    for(int i = 0; i < n; i++){
        arany[i] = van_ilyen1[arany[i]];
        rabszolga[i] = van_ilyen2[rabszolga[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
        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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base60/100
1Elfogadva0/012ms17604 KiB
2Elfogadva0/0153ms54712 KiB
3Elfogadva4/410ms18028 KiB
4Elfogadva4/410ms17984 KiB
5Elfogadva4/410ms18260 KiB
6Elfogadva4/410ms18184 KiB
7Elfogadva4/410ms18448 KiB
8Hibás válasz0/49ms18672 KiB
9Elfogadva4/49ms18784 KiB
10Elfogadva4/410ms19496 KiB
11Elfogadva4/419ms22536 KiB
12Elfogadva4/434ms26224 KiB
13Elfogadva6/632ms25768 KiB
14Elfogadva6/654ms31672 KiB
15Elfogadva6/687ms41464 KiB
16Elfogadva6/6149ms56308 KiB
17Futási hiba0/6180ms63096 KiB
18Futási hiba0/6167ms63040 KiB
19Futási hiba0/6167ms62960 KiB
20Futási hiba0/6153ms62916 KiB
21Futási hiba0/6150ms62900 KiB
22Futási hiba0/6158ms62924 KiB