100762024-03-26 12:37:22Error42Hadjáratcpp17Accepted 100/100119ms8004 KiB
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct city {
    int id, x, y, from;
};

struct hull {
    map<int, city> h;

    hull(city const& n) {
        h[n.x] = n;
    }

    bool inside(city const& n) const {
        auto it = h.lower_bound(n.x);

        if (it == h.begin())
            return false;

        --it;

        return n.y > it->second.y;
    }

    city inside_of(city const& n) const {
        auto it = h.lower_bound(n.x);

        --it;

        return it->second;
    }

    bool outside(city const& n) const {
        auto it = h.upper_bound(n.x);

        if (it == h.begin())
            return true;

        --it;

        if (it->second.x == n.x)
            return false;

        return n.y < it->second.y;
    }

    void insert(city const& n) {
        if (!outside(n))
            return;

        h[n.x] = n;

        auto it = h.find(n.x);

        while (it != h.begin()) {
            auto before = it;
            --before;

            assert(before->second.y != it->second.y);

            if (before->second.y < it->second.y)
                h.erase(before);
            else
                break;
        }

        while (true) {
            auto after = it;
            ++after;

            if (after == h.end())
                break;

            if (after->second.y >= it->second.y)
                h.erase(after);
            else
                break;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<city> cities(n);
    for (int i = 0; i < n; i++) {
        cities[i].id = i;
        cin >> cities[i].x >> cities[i].y;
        cities[i].from = -2;
    }

    vector<hull> lis;

    for (int i = 0; i < n; i++) {
        int const insert = lower_bound(lis.begin(), lis.end(), cities[i], [&](hull const& h, city const& c) {
            return h.inside(c);
        }) - lis.begin();

        if (insert == 0)
            cities[i].from = -1;
        else
            cities[i].from = lis[insert - 1].inside_of(cities[i]).id;

        if (insert == lis.size())
            lis.push_back({ cities[i] });
        else
            lis[insert].insert(cities[i]);
    }

    cout << lis.size() << "\n";

    vector<int> sol;

    int cur = lis.back().h.begin()->second.id;

    while (cur != -1) {
        sol.push_back(cur);
        cur = cities[cur].from;
    }

    reverse(sol.begin(), sol.end());

    for (int const& x : sol)
        cout << x + 1 << " ";
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/03ms1956 KiB
2Accepted0/054ms4032 KiB
3Accepted4/43ms2588 KiB
4Accepted4/43ms2556 KiB
5Accepted4/43ms2692 KiB
6Accepted4/43ms2772 KiB
7Accepted4/43ms2952 KiB
8Accepted4/43ms3048 KiB
9Accepted4/43ms3140 KiB
10Accepted4/43ms3148 KiB
11Accepted4/47ms3496 KiB
12Accepted4/410ms3760 KiB
13Accepted6/610ms3844 KiB
14Accepted6/620ms4456 KiB
15Accepted6/632ms5060 KiB
16Accepted6/654ms5916 KiB
17Accepted6/668ms6432 KiB
18Accepted6/679ms6564 KiB
19Accepted6/693ms7168 KiB
20Accepted6/6119ms7840 KiB
21Accepted6/6119ms7876 KiB
22Accepted6/6119ms8004 KiB