176402025-08-23 13:15:09horkaHadjáratcpp11Time limit exceeded 64/100300ms15796 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=1e5+6;
set<array<int, 2>> fen[c];
int g[c],h[c],n;
void upd(int pos, array<int, 2> x)
{
	array<int, 2> f{x[0],0};
	for(; pos<=n; pos=h[pos])
	{
		if(fen[pos].empty() || x[0]<(*fen[pos].begin())[0])
		{
			fen[pos].insert(x);
			if(fen[pos].size()>1)
			{
				vector<array<int, 2>> tor;
				auto it=fen[pos].begin();
				it++;
				array<int, 2> p=*fen[pos].rbegin();
				while(1)
				{
					if((*it)[1]<=x[1]) tor.push_back(*it);
					else break;
					if(*it==p) break;
					it++;
				}
				for(array<int, 2> &s:tor)
				{
					fen[pos].erase(s);

				}
			}
		}
		else
		{
			auto it=fen[pos].lower_bound(f);
			it--;
			if((*it)[1]<x[1])
			{
				it++;
				vector<array<int, 2>> tor;
				array<int, 2> p=*fen[pos].rbegin();
				if(x>p)
				{
					fen[pos].insert(x);
					continue;
				}
				while(1)
				{
					if((*it)[1]<=x[1]) tor.push_back(*it);
					else break;
					if(*it==p) break;
					it++;
				}
				for(array<int, 2> &s:tor)
				{
					fen[pos].erase(s);
				}
				fen[pos].insert(x);
			} 
		}
	}
}
int query(int pos, int e)
{
	int ans=0;
	array<int, 2> x{e,0};
	for(; pos>=0; pos=g[pos]-1)
	{
		if(!fen[pos].empty() && (*fen[pos].begin())[0]<e)
		{
			auto it=fen[pos].lower_bound(x);
			it--;
			ans=max(ans,(*it)[1]);
		}
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=0; i<=n; i++)
		g[i]=(i&(i+1));
	for(int i=0; i<=n; i++)
		h[i]=(i|(i+1));
	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();
	vector<int> dp(n+1);
	for(int i=1; i<=n; i++)
	{
		int p=query(a[i]-1,b[i]);
		dp[i]=p+1;
		upd(a[i],{b[i],dp[i]});
	}
	int kezd=0;
	for(int i=1; i<=n; i++)
		if(dp[i]>dp[kezd]) kezd=i;
	cout<<dp[kezd]<<"\n";
	vector<int> ans{kezd};
	int kell=dp[kezd]-1;
	for(int i=kezd-1; i>0; i--)
	{
		if(dp[i]==kell && a[i]<a[kezd] && b[i]<b[kezd])
		{
			ans.push_back(i);
			kezd=i,kell--;
		}
	}
	reverse(ans.begin(),ans.end());
	for(int &i:ans)
		cout<<i<<" ";
	cout<<"\n";

}
SubtaskSumTestVerdictTimeMemory
base64/100
1Accepted0/06ms4916 KiB
2Accepted0/0174ms11188 KiB
3Accepted4/46ms5100 KiB
4Accepted4/44ms4916 KiB
5Accepted4/44ms4916 KiB
6Accepted4/44ms4916 KiB
7Accepted4/44ms5108 KiB
8Accepted4/44ms5180 KiB
9Accepted4/44ms4928 KiB
10Accepted4/47ms5364 KiB
11Accepted4/416ms5544 KiB
12Accepted4/428ms6356 KiB
13Accepted6/629ms6044 KiB
14Accepted6/659ms6964 KiB
15Accepted6/693ms8756 KiB
16Accepted6/6180ms11108 KiB
17Time limit exceeded0/6218ms12724 KiB
18Time limit exceeded0/6273ms14220 KiB
19Time limit exceeded0/6300ms15024 KiB
20Time limit exceeded0/6291ms15280 KiB
21Time limit exceeded0/6293ms15796 KiB
22Time limit exceeded0/6287ms15536 KiB