10103 2024. 03. 26 20:44:33 szil Hadjárat cpp17 Elfogadva 100/100 111ms 5768 KiB
#include <bits/stdc++.h>

using ll = long long;
using namespace std;

struct City {
    int x, y, idx;

    City(int a, int b, int c) : x(a), y(b), idx(c) {}

    bool operator<(const City &c) const {
        return x < c.x;
    }
};

const int MAXN = 200'001;

vector<set<City>> dp;
int last[MAXN];

int get_before(const set<City> &s, int x, int y) {
    auto it = s.lower_bound({x, 0, 0});
    if (it != s.begin()) return prev(it)->y < y ? prev(it)->idx : 0;
    return 0;
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        auto it = lower_bound(dp.begin(), dp.end(), make_pair(x, y), [&](const auto &s, auto x){
            return get_before(s, x.first, x.second);
        });
        last[i] = it == dp.begin() ? 0 : get_before(*prev(it), x, y);
        if (it == dp.end()) {
            dp.emplace_back(set<City>{{x, y, i}});
        } else {
            while (true) {
                auto it2 = it->lower_bound({x, 0, 0});
                if (it2 != it->end() && it2->y >= y) it->erase(it2);
                else break;
            }
            it->insert({x, y, i});
        }
    }
    cout << dp.size() << "\n";
    stack<int> ans;
    int idx = dp.back().begin()->idx;
    while (idx) {
        ans.push(idx);
        idx = last[idx];
    }
    while (!ans.empty()) {
        cout << ans.top() << " ";
        ans.pop();
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1832 KiB
2 Elfogadva 0/0 50ms 2940 KiB
3 Elfogadva 4/4 3ms 2360 KiB
4 Elfogadva 4/4 3ms 2580 KiB
5 Elfogadva 4/4 3ms 2552 KiB
6 Elfogadva 4/4 3ms 2632 KiB
7 Elfogadva 4/4 3ms 2764 KiB
8 Elfogadva 4/4 3ms 2972 KiB
9 Elfogadva 4/4 3ms 3212 KiB
10 Elfogadva 4/4 3ms 3340 KiB
11 Elfogadva 4/4 6ms 3596 KiB
12 Elfogadva 4/4 10ms 3720 KiB
13 Elfogadva 6/6 9ms 3724 KiB
14 Elfogadva 6/6 18ms 3788 KiB
15 Elfogadva 6/6 29ms 4132 KiB
16 Elfogadva 6/6 50ms 4736 KiB
17 Elfogadva 6/6 63ms 4740 KiB
18 Elfogadva 6/6 74ms 5200 KiB
19 Elfogadva 6/6 86ms 5208 KiB
20 Elfogadva 6/6 111ms 5748 KiB
21 Elfogadva 6/6 109ms 5768 KiB
22 Elfogadva 6/6 109ms 5752 KiB