168792025-05-15 10:20:09HoraHadjáratcpp17Hibás válasz 96/100165ms1076 KiB
#include <bits/stdc++.h>
using namespace std;

vector<set<array<int, 3>>> lis;
vector<int> p;

void add(array<int, 3> a, set<array<int, 3>>& s){
    s.insert(a);
    auto it = s.upper_bound(a);
    while(it != s.end()){
        if((*it)[1] >= a[1]) it = s.erase(it);
        else break;
    }
}

bool check(array<int, 3> a, set<array<int, 3>>& s){
    auto it = s.lower_bound({a[0], -1});
    if(it == s.begin()) return false;
    it--;
    return ((*it)[1] < a[1]);
}

int index(array<int, 3> a, set<array<int, 3>>& s){
    auto it = s.upper_bound({a[0], -1, -1});
    it--;
    return (*it)[2];
}

void solve(array<int, 3> a){
    int lo = 0, hi = lis.size(), mid;
    while(lo + 1 < hi){
        mid = (lo + hi) / 2;
        if(check(a, lis[mid])) lo = mid;
        else hi = mid;
    }
    if(lo + 1 >= lis.size()) lis.push_back({});
    add(a, lis[lo + 1]);
    p[a[2]] = index(a, lis[lo]);
}


int main() {
    int n;
    cin >> n;
    lis = {{{0, 0, 0}}};
    p.resize(n + 1, 0);
    for(int i = 0; i < n; i++){
        array<int, 3> a;
        cin >> a[0] >> a[1];
        a[2] = i + 1;
        solve(a);
    }
    cout << lis.size() - 1 << "\n";
    int c = (*lis.back().begin())[2];
    vector<int> ans;
    while(c != 0){
        ans.push_back(c);
        c = p[c];
    }
    reverse(ans.begin(), ans.end());
    for(auto x : ans) cout << x << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base96/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/075ms564 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms316 KiB
7Elfogadva4/41ms316 KiB
8Hibás válasz0/41ms316 KiB
9Elfogadva4/41ms316 KiB
10Elfogadva4/42ms316 KiB
11Elfogadva4/47ms468 KiB
12Elfogadva4/414ms316 KiB
13Elfogadva6/613ms316 KiB
14Elfogadva6/627ms520 KiB
15Elfogadva6/643ms560 KiB
16Elfogadva6/675ms668 KiB
17Elfogadva6/696ms708 KiB
18Elfogadva6/6112ms756 KiB
19Elfogadva6/6129ms820 KiB
20Elfogadva6/6165ms1076 KiB
21Elfogadva6/6165ms1076 KiB
22Elfogadva6/6165ms1076 KiB