9932 2024. 03. 18 20:42:13 111 Hadjárat cpp17 Elfogadva 100/100 104ms 15880 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 Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 48ms 8160 KiB
3 Elfogadva 4/4 3ms 2348 KiB
4 Elfogadva 4/4 3ms 2320 KiB
5 Elfogadva 4/4 3ms 2340 KiB
6 Elfogadva 4/4 3ms 2540 KiB
7 Elfogadva 4/4 3ms 2780 KiB
8 Elfogadva 4/4 3ms 2836 KiB
9 Elfogadva 4/4 3ms 2852 KiB
10 Elfogadva 4/4 3ms 3176 KiB
11 Elfogadva 4/4 6ms 3408 KiB
12 Elfogadva 4/4 9ms 4404 KiB
13 Elfogadva 6/6 9ms 4492 KiB
14 Elfogadva 6/6 18ms 5788 KiB
15 Elfogadva 6/6 28ms 6904 KiB
16 Elfogadva 6/6 48ms 9500 KiB
17 Elfogadva 6/6 59ms 10868 KiB
18 Elfogadva 6/6 70ms 12188 KiB
19 Elfogadva 6/6 82ms 13352 KiB
20 Elfogadva 6/6 104ms 15880 KiB
21 Elfogadva 6/6 104ms 15752 KiB
22 Elfogadva 6/6 104ms 15572 KiB