5311 2023. 04. 25 19:32:53 sztomi Hadjárat cpp11 Elfogadva 100/100 105ms 16148 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 varos{
    int a, r, ind;
    bool operator<(const varos &b) const{
        if(b.a == a){
            if(b.r == r){
                return ind < b.ind;
            }
            return r < b.r;
        }
        return a < b.a;
    }
};

int n;
int arany[MAXN];
int rabszolga[MAXN];
int elozo[MAXN];
set<varos> megoldasok[MAXN];

int legkisebb(int mid, int ind){
    /*
    cout << "legkisebb mid: " << mid << " ind: " << ind << "\n";
    for(auto x : megoldasok[mid]){
        cout << x.ind << " ";
    }
    cout << "\n";
    cout << "---------\n";
    */

    if(megoldasok[mid].size() == 0) return -1;
    auto it = megoldasok[mid].lower_bound({arany[ind], -1, -1});
    if(it == megoldasok[mid].begin()) return -1;
    --it;
    // meg az sem jo
    if(rabszolga[ind] <= it->r) return -1;
    return it->ind;
}

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

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

    int legjobb = 0;
    int legjobb_ind = -1;

    int l, r, mid, hely;
    // {mennyi, hol}
    int 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 = legkisebb(mid, i);
            //cout << "kiprobalt mid: " << mid << " " << legkevesebb_szolga << "\n";
            if(legkevesebb_szolga != -1){
                hely = mid;
                elozo[i] = legkevesebb_szolga;
                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(megoldasok[hely+1].size() == 0){
            megoldasok[hely+1].insert({arany[i], rabszolga[i], i});
        }
        else{
            auto it = megoldasok[hely+1].lower_bound({arany[i], rabszolga[i], i});
            // lehetnek esetleg nala jobbak is
            if(it != megoldasok[hely+1].begin()){
                auto elozo = it;
                --elozo;
                if(elozo->a == arany[i] || elozo->r == rabszolga[i]){
                    //cout << "nem rakja bele " << i << "\n";
                    continue;
                }
            }
            it = megoldasok[hely+1].insert(it, {arany[i], rabszolga[i], i});
            ++it;
            // felesleges
            while(it != megoldasok[hely+1].end() && it->r >= rabszolga[i]){
                //cout << it->ind << " torolve\n";
                it = megoldasok[hely+1].erase(it);
            }
        }
        if(legjobb < hely + 1){
            legjobb = hely + 1;
            legjobb_ind = i;
        }
        /*
        cout << "megoldasok[hely+1]: ";
        for(auto x : megoldasok[hely+1]){
            cout << x.ind << " ";
        }
        cout << "\n";
        cout << "-----------------------------------------------------------\n";
        */
    }

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

    for(int i = 0; i < n; i++){
        cout << i << ": " << elozo[i] << "\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 100/100
1 Elfogadva 0/0 7ms 11132 KiB
2 Elfogadva 0/0 50ms 12848 KiB
3 Elfogadva 4/4 6ms 11548 KiB
4 Elfogadva 4/4 7ms 11788 KiB
5 Elfogadva 4/4 6ms 11964 KiB
6 Elfogadva 4/4 6ms 11896 KiB
7 Elfogadva 4/4 6ms 12148 KiB
8 Elfogadva 4/4 6ms 12100 KiB
9 Elfogadva 4/4 6ms 12244 KiB
10 Elfogadva 4/4 6ms 12652 KiB
11 Elfogadva 4/4 8ms 12820 KiB
12 Elfogadva 4/4 13ms 13120 KiB
13 Elfogadva 6/6 13ms 13056 KiB
14 Elfogadva 6/6 20ms 13340 KiB
15 Elfogadva 6/6 29ms 13752 KiB
16 Elfogadva 6/6 50ms 14424 KiB
17 Elfogadva 6/6 61ms 14800 KiB
18 Elfogadva 6/6 71ms 15304 KiB
19 Elfogadva 6/6 82ms 15652 KiB
20 Elfogadva 6/6 104ms 16148 KiB
21 Elfogadva 6/6 105ms 16100 KiB
22 Elfogadva 6/6 104ms 16076 KiB