10102 2024. 03. 26 20:41:45 szil Hadjárat cpp17 Hibás válasz 79/100 112ms 5636 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 {
        if (x == c.x) return y < c.y;
        return x < c.x;
    }
};

const int MAXN = 100'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, y, 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, y, 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 79/100
1 Elfogadva 0/0 3ms 1704 KiB
2 Elfogadva 0/0 52ms 2780 KiB
3 Elfogadva 4/4 2ms 1956 KiB
4 Elfogadva 4/4 3ms 2084 KiB
5 Elfogadva 4/4 2ms 2172 KiB
6 Elfogadva 4/4 3ms 2300 KiB
7 Elfogadva 4/4 3ms 2512 KiB
8 Hibás válasz 0/4 3ms 2996 KiB
9 Részben helyes 2/4 3ms 3148 KiB
10 Elfogadva 4/4 3ms 3024 KiB
11 Elfogadva 4/4 7ms 3364 KiB
12 Elfogadva 4/4 10ms 3616 KiB
13 Elfogadva 6/6 10ms 3832 KiB
14 Hibás válasz 0/6 19ms 3968 KiB
15 Elfogadva 6/6 29ms 4428 KiB
16 Részben helyes 3/6 52ms 4904 KiB
17 Részben helyes 3/6 64ms 4908 KiB
18 Elfogadva 6/6 75ms 5108 KiB
19 Részben helyes 3/6 89ms 5420 KiB
20 Elfogadva 6/6 112ms 5632 KiB
21 Elfogadva 6/6 112ms 5636 KiB
22 Elfogadva 6/6 112ms 5628 KiB