99322024-03-18 20:42:13111Hadjáratcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/03ms1828 KiB
2Elfogadva0/048ms8160 KiB
3Elfogadva4/43ms2348 KiB
4Elfogadva4/43ms2320 KiB
5Elfogadva4/43ms2340 KiB
6Elfogadva4/43ms2540 KiB
7Elfogadva4/43ms2780 KiB
8Elfogadva4/43ms2836 KiB
9Elfogadva4/43ms2852 KiB
10Elfogadva4/43ms3176 KiB
11Elfogadva4/46ms3408 KiB
12Elfogadva4/49ms4404 KiB
13Elfogadva6/69ms4492 KiB
14Elfogadva6/618ms5788 KiB
15Elfogadva6/628ms6904 KiB
16Elfogadva6/648ms9500 KiB
17Elfogadva6/659ms10868 KiB
18Elfogadva6/670ms12188 KiB
19Elfogadva6/682ms13352 KiB
20Elfogadva6/6104ms15880 KiB
21Elfogadva6/6104ms15752 KiB
22Elfogadva6/6104ms15572 KiB