1355 2022. 05. 22 13:48:23 Szin Attila Hadjárat cpp14 Elfogadva 100/100 97ms 21416 KiB
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;

struct city {
    int a,b,ind;


    bool operator<(const city& temp) const {
        return a < temp.a;
    }
};


int n, mo, moind;
vector<set<city>> v;
vector<int> p;
stack <int> ki; //NEM VAGYOK ERETNEK

int main() {

#pragma region
#ifndef ONLINE_JUDGE
   freopen("../input.txt", "r", stdin);
   freopen("../output.txt", "w", stdout);
#endif

   InTheNameOfGod;
#pragma endregion
    
    cin >> n;

    v.resize(n+2);
    p.resize(n+2, -1);

    v[0].insert({0, 0, 0});

    for(int i = 1; i <= n; i++) {
        int a,b;
        cin >> a >> b;

        city cur = {a, b, i};

        int l = 0, r = mo, veg = 0, id = -1;
        while(l <= r) {
            int mid = (l + r) / 2, temp = -1;
            
            auto it = v[mid].lower_bound(cur);
            if(it != v[mid].begin() && (--it) -> b < b) temp = it -> ind;
            /*cout << "lower_bound: " << it -> ind << endl;    
            cout << mid << ": " << temp << endl;*/

            if(temp != -1) {
                veg = mid;
                l = mid+1;
                id = temp;
            }
            else {
                r = mid-1;
            }
        }

        //cout << i << ": " << veg << endl;

        p[i] = id;
        veg++;
        if(veg > mo) {
            mo = veg;
            moind = i;
        }
        auto it = v[veg].lower_bound(cur);
        while (it != v[veg].end() && it -> b >= b) {
            it = v[veg].erase(it);
        }
        if(it == v[veg].end() || it->a > a) v[veg].insert(cur);
    }

    cout << mo << "\n";
    int cur = moind;
    while(cur != 0) {
        ki.push(cur);
        cur = p[cur];
    }

    while(!ki.empty()) {
        cout << ki.top() << ' ';
        ki.pop();
    }

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 2ms 1772 KiB
2 Elfogadva 0/0 41ms 7824 KiB
3 Elfogadva 4/4 1ms 2440 KiB
4 Elfogadva 4/4 1ms 2448 KiB
5 Elfogadva 4/4 1ms 2448 KiB
6 Elfogadva 4/4 1ms 2456 KiB
7 Elfogadva 4/4 1ms 2460 KiB
8 Elfogadva 4/4 2ms 2468 KiB
9 Elfogadva 4/4 2ms 2484 KiB
10 Elfogadva 4/4 2ms 2540 KiB
11 Elfogadva 4/4 4ms 2936 KiB
12 Elfogadva 4/4 8ms 3500 KiB
13 Elfogadva 6/6 8ms 3620 KiB
14 Elfogadva 6/6 16ms 4888 KiB
15 Elfogadva 6/6 24ms 6240 KiB
16 Elfogadva 6/6 43ms 9320 KiB
17 Elfogadva 6/6 56ms 11200 KiB
18 Elfogadva 6/6 78ms 13172 KiB
19 Elfogadva 6/6 71ms 15288 KiB
20 Elfogadva 6/6 93ms 18708 KiB
21 Elfogadva 6/6 97ms 20192 KiB
22 Elfogadva 6/6 97ms 21416 KiB