176352025-08-23 10:32:13horkaHadjáratcpp17Időlimit túllépés 58/100301ms30384 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=50000+6;
vector<set<array<int, 2>>> val; //b[i],dp[i],i
int n;
void upd(int cs, int tl, int tr, int pos, array<int, 2> 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, 2>> tor;
		it++;
		array<int, 2> 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, 2>> tor;
		array<int, 2> 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, 2> query(int cs, int tl, int tr, int l, int r, int e)
{
	if(l>r) return {0,0};
	if(l==tl && r==tr)
	{
		if(val[cs].empty() || (*val[cs].rbegin())[0]<=e) return {0,0};
	    return *(val[cs].upper_bound({e,n+10}));
	}
		
	int mid=(tl+tr)/2;
	array<int, 2> a=query(2*cs,tl,mid,l,min(r,mid),e);
	array<int, 2> 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();
	val.resize(4*(mer+1)+5);
	upd(1,1,mer,mer,{0,0});
	vector<int> dp(n+1);
	for(int i=n; i>0; i--)
	{
		array<int, 2> x=query(1,1,mer,a[i]+1,mer,b[i]);
		dp[i]=x[1]+1;
		upd(1,1,mer,a[i],{b[i],dp[i]});
	}
	int kezd=0;
	for(int i=1; i<=n; i++)
		if(dp[i]>dp[kezd]) kezd=i;
	vector<int> ans{kezd};
	cout<<dp[kezd]<<"\n"<<kezd<<" ";
	int kell=dp[kezd]-1;
	for(int i=kezd+1; i<=n; i++)
	{
		if(dp[i]==kell && a[i]>a[kezd] && b[i]>b[kezd])
		{
			cout<<i<<" ";
			kezd=i;
			kell--;
		}
	}
	cout<<"\n";
	

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base58/100
1Elfogadva0/01ms316 KiB
2Időlimit túllépés0/0282ms17844 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms316 KiB
7Elfogadva4/41ms316 KiB
8Elfogadva4/41ms316 KiB
9Elfogadva4/41ms316 KiB
10Elfogadva4/44ms628 KiB
11Elfogadva4/418ms2316 KiB
12Elfogadva4/443ms4404 KiB
13Elfogadva6/641ms3432 KiB
14Elfogadva6/692ms5188 KiB
15Elfogadva6/6175ms11828 KiB
16Időlimit túllépés0/6284ms17588 KiB
17Időlimit túllépés0/6289ms22452 KiB
18Időlimit túllépés0/6289ms24496 KiB
19Időlimit túllépés0/6301ms26932 KiB
20Időlimit túllépés0/6277ms29816 KiB
21Időlimit túllépés0/6289ms30384 KiB
22Időlimit túllépés0/6287ms30384 KiB