53112023-04-25 19:32:53sztomiHadjáratcpp11Elfogadva 100/100105ms16148 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ÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/07ms11132 KiB
2Elfogadva0/050ms12848 KiB
3Elfogadva4/46ms11548 KiB
4Elfogadva4/47ms11788 KiB
5Elfogadva4/46ms11964 KiB
6Elfogadva4/46ms11896 KiB
7Elfogadva4/46ms12148 KiB
8Elfogadva4/46ms12100 KiB
9Elfogadva4/46ms12244 KiB
10Elfogadva4/46ms12652 KiB
11Elfogadva4/48ms12820 KiB
12Elfogadva4/413ms13120 KiB
13Elfogadva6/613ms13056 KiB
14Elfogadva6/620ms13340 KiB
15Elfogadva6/629ms13752 KiB
16Elfogadva6/650ms14424 KiB
17Elfogadva6/661ms14800 KiB
18Elfogadva6/671ms15304 KiB
19Elfogadva6/682ms15652 KiB
20Elfogadva6/6104ms16148 KiB
21Elfogadva6/6105ms16100 KiB
22Elfogadva6/6104ms16076 KiB