101022024-03-26 20:41:45szilHadjáratcpp17Hibás válasz 79/100112ms5636 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ÖsszpontTesztVerdiktIdőMemória
base79/100
1Elfogadva0/03ms1704 KiB
2Elfogadva0/052ms2780 KiB
3Elfogadva4/42ms1956 KiB
4Elfogadva4/43ms2084 KiB
5Elfogadva4/42ms2172 KiB
6Elfogadva4/43ms2300 KiB
7Elfogadva4/43ms2512 KiB
8Hibás válasz0/43ms2996 KiB
9Részben helyes2/43ms3148 KiB
10Elfogadva4/43ms3024 KiB
11Elfogadva4/47ms3364 KiB
12Elfogadva4/410ms3616 KiB
13Elfogadva6/610ms3832 KiB
14Hibás válasz0/619ms3968 KiB
15Elfogadva6/629ms4428 KiB
16Részben helyes3/652ms4904 KiB
17Részben helyes3/664ms4908 KiB
18Elfogadva6/675ms5108 KiB
19Részben helyes3/689ms5420 KiB
20Elfogadva6/6112ms5632 KiB
21Elfogadva6/6112ms5636 KiB
22Elfogadva6/6112ms5628 KiB