176422025-08-23 14:50:44horkaHadjáratcpp17Elfogadva 100/100126ms1840 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	vector<int> a(n+1),b(n+1);
	for(int i=1; i<=n; i++)
		cin>>a[i]>>b[i];
	vector<set<array<int, 2>>> h(2);
	vector<int> dp(n+1);
	dp[1]=1;
	h[0].insert({0,0});
	h[1].insert({a[1],b[1]});
	for(int i=1; i<=n; i++)
	{
		int lo=0,hi=h.size();
		array<int, 2> p{a[i],0};
		while(lo<hi-1)
		{
			int mid=(lo+hi)/2;
			auto it=h[mid].lower_bound(p);
			if(*it==*h[mid].begin())
			{
				hi=mid;
				continue;
			}
			it--;
			if((*it)[1]<b[i]) lo=mid;
			else hi=mid;
		}
		dp[i]=hi;
		if(hi==h.size())
		{
			h.push_back({});
			h.back().insert({a[i],b[i]});
		}
		else
		{
			array<int, 2> x{a[i],b[i]};
			if(x<*h[hi].begin())
			{
				h[hi].insert(x);
				auto it=h[hi].begin();
				array<int, 2> s=*h[hi].rbegin();
				it++;
				vector<array<int, 2>> tor;
				while(1)
				{
					if((*it)[1]>=x[1]) tor.push_back(*it);
					else break;
					if(*it==s) break;
					it++;
				}
				for(array<int, 2> &s:tor)
					h[hi].erase(s);
			}
			else
			{
				if(h[hi].count(x)) continue;
				auto it=h[hi].upper_bound(x);
				it--;
				if((*it)[1]>x[1])
				{
					vector<array<int, 2>> tor;
					it++;
					array<int, 2> s=*h[hi].rbegin();
					while(1)
					{
						if((*it)[1]>=x[1]) tor.push_back(*it);
						else break;
						if(*it==s) break;
						it++;
					}
					for(array<int, 2> &s:tor)
						h[hi].erase(s);
					h[hi].insert(x);
				}
			}
		}
	}
	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";
	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])
		{
			kell--;
			ans.push_back(i);
			kezd=i;
		}
	}
	reverse(ans.begin(),ans.end());
	for(int i:ans)
		cout<<i<<" ";
	cout<<"\n";
}
 
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/057ms1076 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms316 KiB
7Elfogadva4/41ms316 KiB
8Elfogadva4/41ms512 KiB
9Elfogadva4/41ms316 KiB
10Elfogadva4/42ms316 KiB
11Elfogadva4/44ms316 KiB
12Elfogadva4/49ms568 KiB
13Elfogadva6/69ms592 KiB
14Elfogadva6/620ms692 KiB
15Elfogadva6/632ms868 KiB
16Elfogadva6/657ms1076 KiB
17Elfogadva6/671ms1180 KiB
18Elfogadva6/683ms1260 KiB
19Elfogadva6/698ms1484 KiB
20Elfogadva6/6126ms1840 KiB
21Elfogadva6/6126ms1732 KiB
22Elfogadva6/6125ms1756 KiB