101012024-03-26 20:38:29szilHadjáratcpp17Wrong answer 96/100111ms5968 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->upper_bound({x, MAXN, MAXN});
                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;
}
SubtaskSumTestVerdictTimeMemory
base96/100
1Accepted0/03ms1840 KiB
2Accepted0/050ms2956 KiB
3Accepted4/43ms2376 KiB
4Accepted4/43ms2572 KiB
5Accepted4/43ms2664 KiB
6Accepted4/42ms2748 KiB
7Accepted4/43ms2876 KiB
8Wrong answer0/43ms2980 KiB
9Accepted4/43ms3188 KiB
10Accepted4/43ms3296 KiB
11Accepted4/46ms3344 KiB
12Accepted4/410ms3528 KiB
13Accepted6/69ms3756 KiB
14Accepted6/618ms3892 KiB
15Accepted6/629ms4232 KiB
16Accepted6/650ms4480 KiB
17Accepted6/664ms4788 KiB
18Accepted6/675ms5200 KiB
19Accepted6/686ms5580 KiB
20Accepted6/6109ms5684 KiB
21Accepted6/6111ms5968 KiB
22Accepted6/6109ms5880 KiB