113542024-08-22 11:01:19HoraHadjáratcpp17Wrong answer 4/100172ms888 KiB
#include<iostream>
#include<array>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

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

bool query(array<int, 3> a, int x){
    array<int, 3> s = {a[0], -1, -1};
    auto it = lower_bound(lis[x].begin(), lis[x].end(), s);
    if(it != lis[x].begin()) it--;
    return a[1] > (*it)[1];
}

int idquery(array<int, 3> a, int x){
    if(x == 0) return -1;
    array<int, 3> s = {a[0], -1, -1};
    auto it = lower_bound(lis[x].begin(), lis[x].end(), s);
    if(it != lis[x].begin()) it--;
    return (*it)[2];
}

void add(array<int, 3> a, int x){
    lis[x].insert(a);
    auto it = upper_bound(lis[x].begin(), lis[x].end(), a);
    while(it != lis[x].end()){
        it = lis[x].erase(it);
    }
}

int main(){
    int n;
    cin >> n;
    lis.push_back({{0, 0, 0}});
    parent.resize(n);
    for(int i = 0; i < n; i++){
        array<int, 3> a;
        cin >> a[0] >> a[1];
        a[2] = i;
        int lo = 0, hi = lis.size(), mid;
        while(lo + 1 < hi){
            mid = (lo + hi) / 2;
            if(query(a, mid)) lo = mid;
            else hi = mid;
        }
        parent[i] = idquery(a, lo);
        if(lo + 1 == lis.size()){
            lis.push_back({a});
        }
        else add(a, lo + 1);
    }
    cout << lis.size() - 1 << "\n";
    int m = (*lis[lis.size() - 1].begin())[2];
    vector<int> ans;
    while(m != -1){
        ans.push_back(m + 1);
        m = parent[m];
    }
    reverse(ans.begin(), ans.end());
    for(auto x : ans) cout << x << " ";
}
SubtaskSumTestVerdictTimeMemory
base4/100
1Accepted0/03ms384 KiB
2Wrong answer0/079ms764 KiB
3Wrong answer0/43ms356 KiB
4Wrong answer0/43ms500 KiB
5Wrong answer0/43ms292 KiB
6Partially correct2/43ms384 KiB
7Wrong answer0/42ms228 KiB
8Wrong answer0/43ms504 KiB
9Wrong answer0/43ms256 KiB
10Partially correct2/44ms356 KiB
11Wrong answer0/48ms356 KiB
12Wrong answer0/417ms376 KiB
13Wrong answer0/616ms540 KiB
14Wrong answer0/630ms504 KiB
15Wrong answer0/648ms520 KiB
16Wrong answer0/679ms484 KiB
17Wrong answer0/6100ms632 KiB
18Wrong answer0/6119ms612 KiB
19Wrong answer0/6136ms632 KiB
20Wrong answer0/6168ms740 KiB
21Wrong answer0/6171ms740 KiB
22Wrong answer0/6172ms888 KiB