176372025-08-23 11:55:33tomi7Hadjáratcpp17Runtime error 0/10014ms11840 KiB
#include <bits/stdc++.h>
using namespace std;


struct pos{
int a = 0, b = 0;

int i = -1;
};

istream& operator>>(istream& in, pos &p){
in >> p.a >> p.b;
}

bool operator>(const pos& lhs, const pos& rhs){
if(lhs.a != rhs.a) return lhs.a > rhs.a;
if(lhs.b != rhs.b) return lhs.b > rhs.b;
return false;
}

bool operator<(const pos& lhs, const pos& rhs){
if(lhs.a != rhs.a) return lhs.a < rhs.a;
if(lhs.b != rhs.b) return lhs.b < rhs.b;
return false;
}

int main(){
int n;
cin >> n;

vector<set<pos>> last(n+1);
vector<int> prev(n);
pos temp;
last[0].insert(temp);

temp.a = INT_MAX;
temp.b = INT_MAX;
temp.i = -2;

for(auto &s : last) s.insert(temp);

int Max = 0;
int Maxi = -1;

for(int i = 0; i != n; i++){
pos curr;
cin >> curr;
curr.i = i;

int a = 0;
int b = n+1;

while(a+1 != b){
int c = (a+b)/2;

auto iter = lower_bound(last[c].begin(), last[c].end(), curr); iter--;

if(iter->b < curr.b) a = c;
else b = c;
}

auto iter = lower_bound(last[a].begin(), last[a].end(), curr); iter--;


prev[i] = iter->i;

auto nextgr = lower_bound(last[a+1].begin(), last[a+1].end(), curr);

while(nextgr->b >= curr.b) nextgr = last[a+1].erase(nextgr);

last[a+1].insert(curr);

if(a+1 > Max){Max = a+1; Maxi = i;}
}

vector<int> out;

while(Maxi != -1){
out.push_back(Maxi);
Maxi = prev[Maxi];
}

reverse(out.begin(), out.end());

printf("%d\n", out.size());
for(int i : out) printf("%d ", i+1);


return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/100
1Runtime error0/01ms316 KiB
2Runtime error0/08ms5940 KiB
3Runtime error0/41ms316 KiB
4Runtime error0/41ms316 KiB
5Runtime error0/41ms316 KiB
6Runtime error0/41ms316 KiB
7Runtime error0/41ms316 KiB
8Runtime error0/41ms316 KiB
9Runtime error0/41ms316 KiB
10Runtime error0/41ms756 KiB
11Runtime error0/41ms820 KiB
12Runtime error0/43ms1588 KiB
13Runtime error0/63ms1588 KiB
14Runtime error0/63ms2680 KiB
15Runtime error0/64ms3636 KiB
16Runtime error0/68ms5944 KiB
17Runtime error0/68ms7380 KiB
18Runtime error0/610ms8248 KiB
19Runtime error0/610ms9460 KiB
20Runtime error0/614ms11572 KiB
21Runtime error0/613ms11572 KiB
22Runtime error0/613ms11840 KiB