168782025-05-15 10:19:10HoraHadjáratcpp17Wrong answer 82/100165ms1092 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, -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 = -1, 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]);
    if(lo != -1) p[a[2]] = index(a, lis[lo]);
}


int main() {
    int n;
    cin >> n;
    lis = {{{0, 0, 0}}};
    p.resize(n + 1);
    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 << " ";
}
SubtaskSumTestVerdictTimeMemory
base82/100
1Accepted0/01ms316 KiB
2Accepted0/075ms668 KiB
3Accepted4/41ms316 KiB
4Accepted4/41ms316 KiB
5Accepted4/41ms500 KiB
6Accepted4/41ms316 KiB
7Accepted4/41ms316 KiB
8Wrong answer0/41ms316 KiB
9Partially correct2/41ms316 KiB
10Accepted4/42ms316 KiB
11Accepted4/47ms316 KiB
12Accepted4/414ms472 KiB
13Accepted6/613ms492 KiB
14Wrong answer0/626ms576 KiB
15Accepted6/643ms652 KiB
16Partially correct3/675ms664 KiB
17Accepted6/697ms720 KiB
18Accepted6/6112ms824 KiB
19Partially correct3/6129ms740 KiB
20Accepted6/6165ms1076 KiB
21Accepted6/6165ms1092 KiB
22Accepted6/6164ms1076 KiB