100752024-03-26 12:34:32Error42Hadjáratcpp17Runtime error 24/10050ms15572 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;

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

            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
base24/100
1Accepted0/03ms1956 KiB
2Runtime error0/017ms4488 KiB
3Accepted4/43ms2808 KiB
4Accepted4/43ms3032 KiB
5Accepted4/43ms3248 KiB
6Accepted4/43ms3536 KiB
7Accepted4/43ms3516 KiB
8Runtime error0/43ms3612 KiB
9Runtime error0/43ms3796 KiB
10Accepted4/43ms3836 KiB
11Runtime error0/46ms4108 KiB
12Runtime error0/47ms4372 KiB
13Runtime error0/64ms4604 KiB
14Runtime error0/67ms5184 KiB
15Runtime error0/69ms5760 KiB
16Runtime error0/616ms7076 KiB
17Runtime error0/623ms8220 KiB
18Runtime error0/637ms9744 KiB
19Runtime error0/635ms11144 KiB
20Runtime error0/650ms13216 KiB
21Runtime error0/637ms14212 KiB
22Runtime error0/639ms15572 KiB