176312025-08-22 15:49:34horkaHadjáratcpp17Runtime error 16/10083ms32000 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=10000+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
base16/100
1Accepted0/03ms2100 KiB
2Runtime error0/039ms3252 KiB
3Wrong answer0/43ms2100 KiB
4Accepted4/43ms2100 KiB
5Accepted4/42ms2100 KiB
6Wrong answer0/43ms2100 KiB
7Accepted4/42ms2272 KiB
8Wrong answer0/43ms2292 KiB
9Accepted4/43ms2100 KiB
10Wrong answer0/44ms2548 KiB
11Wrong answer0/48ms2448 KiB
12Runtime error0/48ms2600 KiB
13Runtime error0/661ms32000 KiB
14Runtime error0/683ms32000 KiB
15Runtime error0/623ms2868 KiB
16Runtime error0/637ms3252 KiB
17Runtime error0/648ms3248 KiB
18Runtime error0/657ms4016 KiB
19Runtime error0/664ms4016 KiB
20Runtime error0/679ms4044 KiB
21Runtime error0/679ms4016 KiB
22Runtime error0/679ms4016 KiB