101032024-03-26 20:44:33szilHadjáratcpp17Accepted 100/100111ms5768 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;
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/03ms1832 KiB
2Accepted0/050ms2940 KiB
3Accepted4/43ms2360 KiB
4Accepted4/43ms2580 KiB
5Accepted4/43ms2552 KiB
6Accepted4/43ms2632 KiB
7Accepted4/43ms2764 KiB
8Accepted4/43ms2972 KiB
9Accepted4/43ms3212 KiB
10Accepted4/43ms3340 KiB
11Accepted4/46ms3596 KiB
12Accepted4/410ms3720 KiB
13Accepted6/69ms3724 KiB
14Accepted6/618ms3788 KiB
15Accepted6/629ms4132 KiB
16Accepted6/650ms4736 KiB
17Accepted6/663ms4740 KiB
18Accepted6/674ms5200 KiB
19Accepted6/686ms5208 KiB
20Accepted6/6111ms5748 KiB
21Accepted6/6109ms5768 KiB
22Accepted6/6109ms5752 KiB