176332025-08-23 08:00:59horkaHadjáratcpp17Time limit exceeded 52/100301ms32000 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=1e5+6;
set<array<int, 3>> val[4*c]; //b[i],dp[i],i
int n;
array<int, 3> tmp{7,1,1};
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);
		if(val[cs].size()>1){
		auto it=val[cs].rbegin();
		vector<array<int, 3>> tor;
		it++;
		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);

		}
		}
	}
	else
	{
		auto it=val[cs].lower_bound(x);
		if(x[1]>(*it)[1]){
		it--;
		vector<array<int, 3>> tor;
		array<int, 3> p=*val[cs].begin();
		if(x>p){
		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)
	{
		if(val[cs].empty() || (*val[cs].rbegin())[0]<=e) return {0,0,0};
	    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]);
	}
	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();
	}
	int mer=pontok.size();
	upd(1,1,mer,mer,{0,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!=0)
	{
		ans.push_back(kezd);
		kezd=dp[kezd][1];
	}
	cout<<(int)ans.size()<<"\n";
	for(int i:ans)
		cout<<i<<" ";
	cout<<"\n";

}
SubtaskSumTestVerdictTimeMemory
base52/100
1Accepted0/018ms18996 KiB
2Time limit exceeded0/0275ms31668 KiB
3Accepted4/416ms18996 KiB
4Accepted4/420ms19000 KiB
5Accepted4/419ms18996 KiB
6Accepted4/416ms19008 KiB
7Accepted4/416ms19012 KiB
8Accepted4/416ms19192 KiB
9Accepted4/419ms19228 KiB
10Accepted4/423ms19256 KiB
11Accepted4/439ms20536 KiB
12Accepted4/464ms22024 KiB
13Accepted6/657ms21556 KiB
14Accepted6/6111ms23688 KiB
15Time limit exceeded0/6208ms27900 KiB
16Time limit exceeded0/6301ms31620 KiB
17Time limit exceeded0/6248ms32000 KiB
18Time limit exceeded0/6241ms32000 KiB
19Time limit exceeded0/6256ms32000 KiB
20Time limit exceeded0/6224ms32000 KiB
21Time limit exceeded0/6240ms32000 KiB
22Time limit exceeded0/6224ms32000 KiB