99322024-03-18 20:42:13111Hadjáratcpp17Accepted 100/100104ms15880 KiB
#include <bits/stdc++.h>
using namespace std;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("be2.txt","r",stdin);
//	freopen("out.txt","w",stdout);
#endif
	int N;
	cin>>N;
	vector<int>r(N+1),a(N+1),p(N,-1);
	for(int i=0;i<N;i++){
		cin>>r[i]>>a[i];
	}
	vector<multimap<int,int>>v(N+1);
	v[0].emplace(0,N);
	for(int i=0;i<N;i++){
		int l=0,h=i+1;
		while(l!=h){
			int m=(l+h)/2;
			auto it=v[m].lower_bound(r[i]);
			if(it==v[m].begin()){
				h=m;
				continue;
			}
			it--;
			if(a[it->second]>=a[i]){
				h=m;
				continue;
			}
			p[i]=it->second;
			l=m+1;
		}
		auto it=v[l].emplace(r[i],i);
		if(it!=v[l].begin()&&a[it->second]>=a[prev(it)->second]){
			v[l].erase(it);
			continue;
		}
		it++;
		while(it!=v[l].end()&&a[it->second]>=a[i]){
			it=v[l].erase(it);
		}
	}
	int ans=N;
	while(v[ans].empty())ans--;
	cout<<ans<<'\n';
	vector<int>anss;
	for(int i=v[ans].begin()->second;i!=N;i=p[i])anss.push_back(i);
	reverse(anss.begin(),anss.end());
	for(int i:anss)cout<<i+1<<' ';cout<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/03ms1828 KiB
2Accepted0/048ms8160 KiB
3Accepted4/43ms2348 KiB
4Accepted4/43ms2320 KiB
5Accepted4/43ms2340 KiB
6Accepted4/43ms2540 KiB
7Accepted4/43ms2780 KiB
8Accepted4/43ms2836 KiB
9Accepted4/43ms2852 KiB
10Accepted4/43ms3176 KiB
11Accepted4/46ms3408 KiB
12Accepted4/49ms4404 KiB
13Accepted6/69ms4492 KiB
14Accepted6/618ms5788 KiB
15Accepted6/628ms6904 KiB
16Accepted6/648ms9500 KiB
17Accepted6/659ms10868 KiB
18Accepted6/670ms12188 KiB
19Accepted6/682ms13352 KiB
20Accepted6/6104ms15880 KiB
21Accepted6/6104ms15752 KiB
22Accepted6/6104ms15572 KiB