176292025-08-22 15:48:12horkaHadjáratcpp17Runtime error 0/10030ms32000 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=2e5+6;
set<array<int, 3>> val[4*c]; //b[i],dp[i],i
int n;
void upd(int cs, int tl, int tr, int pos, array<int, 3> x)
{
	if(val[cs].empty() || x[0]>(*val[cs].rbegin())[0])
	{
		val[cs].insert(x);
	}
	else
	{
		auto it=val[cs].lower_bound(x);
		if((*it)[1]>=x[1])
		{
			return;
		}
		it--;
		vector<array<int, 3>> tor;
		array<int, 3> p=*val[cs].begin();
		while(1)
		{
			if((*it)[1]<=x[1]) tor.push_back(*it);
			else break;
			if(*it==p) break;
			it--;
		}
		for(auto &s:tor)
			val[cs].erase(s);
		val[cs].insert(x);
		
	}
	if(tl==tr) return;
	int mid=(tl+tr)/2;
	if(pos<=mid) upd(2*cs,tl,mid,pos,x);
	else upd(2*cs+1,mid+1,tr,pos,x);
}
array<int, 3> query(int cs, int tl, int tr, int l, int r, int e)
{
	if(l>r) return {0,0,0};
	if(l==tl && r==tr) return *(val[cs].upper_bound({e,n+10,e}));
	int mid=(tl+tr)/2;
	array<int, 3> a=query(2*cs,tl,mid,l,min(r,mid),e);
	array<int, 3> b=query(2*cs+1,mid+1,tr,max(mid+1,l),r,e);
	if(a[1]>b[1]) return a;
	else return b;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	vector<int> pontok{0},a(n+1),b(n+1);
	for(int i=1; i<=n; i++)
	{
		cin>>a[i]>>b[i];
		pontok.push_back(a[i]);
		pontok.push_back(b[i]);
	}
	sort(pontok.begin(),pontok.end());
	pontok.erase(unique(pontok.begin(),pontok.end()),pontok.end());
	for(int i=1; i<=n; i++)
	{
		a[i]=lower_bound(pontok.begin(),pontok.end(),a[i])-pontok.begin();
		b[i]=lower_bound(pontok.begin(),pontok.end(),b[i])-pontok.begin();
	}
	int mer=pontok.size();
	upd(1,1,mer,mer,{mer,0,n+1});
	vector<array<int, 2>> dp(n+1);
	for(int i=n; i>0; i--)
	{
		array<int, 3> x=query(1,1,mer,a[i]+1,mer,b[i]);
		dp[i]={x[1]+1,x[2]};
		upd(1,1,mer,a[i],{b[i],dp[i][0],i});
	}
	int kezd=0;
	for(int i=1; i<=n; i++)
		if(dp[i][0]>dp[kezd][0]) kezd=i;
	vector<int> ans;
	while(kezd<=n)
	{
		ans.push_back(kezd);
		kezd=dp[kezd][1];
	}
	cout<<(int)ans.size()<<"\n";
	for(int i:ans)
		cout<<i<<" ";
	cout<<"\n";

}
SubtaskSumTestVerdictTimeMemory
base0/100
1Runtime error0/024ms32000 KiB
2Runtime error0/029ms32000 KiB
3Runtime error0/429ms32000 KiB
4Runtime error0/425ms32000 KiB
5Runtime error0/429ms32000 KiB
6Runtime error0/425ms32000 KiB
7Runtime error0/429ms32000 KiB
8Runtime error0/425ms32000 KiB
9Runtime error0/425ms32000 KiB
10Runtime error0/430ms32000 KiB
11Runtime error0/429ms32000 KiB
12Runtime error0/425ms32000 KiB
13Runtime error0/630ms32000 KiB
14Runtime error0/626ms32000 KiB
15Runtime error0/624ms32000 KiB
16Runtime error0/629ms32000 KiB
17Runtime error0/630ms32000 KiB
18Runtime error0/624ms32000 KiB
19Runtime error0/624ms32000 KiB
20Runtime error0/629ms32000 KiB
21Runtime error0/628ms32000 KiB
22Runtime error0/623ms32000 KiB