176302025-08-22 15:48:49horkaHadjáratcpp17Futási hiba 16/10079ms3504 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=1000+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";

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base16/100
1Elfogadva0/01ms588 KiB
2Futási hiba0/037ms2228 KiB
3Hibás válasz0/41ms568 KiB
4Elfogadva4/41ms572 KiB
5Elfogadva4/41ms756 KiB
6Hibás válasz0/41ms584 KiB
7Elfogadva4/41ms380 KiB
8Hibás válasz0/41ms576 KiB
9Elfogadva4/42ms576 KiB
10Futási hiba0/42ms576 KiB
11Futási hiba0/44ms824 KiB
12Futási hiba0/48ms1036 KiB
13Futási hiba0/67ms824 KiB
14Futási hiba0/614ms1268 KiB
15Futási hiba0/621ms1588 KiB
16Futási hiba0/637ms2176 KiB
17Futási hiba0/646ms2480 KiB
18Futási hiba0/654ms3172 KiB
19Futási hiba0/663ms3248 KiB
20Futási hiba0/679ms3504 KiB
21Futási hiba0/679ms3504 KiB
22Futási hiba0/679ms3504 KiB