176362025-08-23 11:06:47horkaHadjáratcpp17Hibás válasz 37/100289ms14700 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)
{
	for(; pos<=n; pos=h[pos])
	{
		if(fen[pos].empty() || x[0]<(*fen[pos].begin())[0])
		{
			fen[pos].insert(x);
			vector<array<int, 2>> tor;
			if(fen[pos].size()>1)
			{
				auto it=fen[pos].begin();
				it++;
				array<int, 2> p=*fen[pos].rbegin();
				vector<array<int, 2>> tor;
				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(x);
			it--;
			if((*it)[1]<x[1])
			{
				it++;
				vector<array<int, 2>> tor;
				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);
				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],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";

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base37/100
1Elfogadva0/06ms4916 KiB
2Elfogadva0/0182ms10676 KiB
3Elfogadva4/46ms4916 KiB
4Elfogadva4/44ms4916 KiB
5Elfogadva4/46ms4960 KiB
6Elfogadva4/44ms4916 KiB
7Elfogadva4/46ms4916 KiB
8Hibás válasz0/46ms4916 KiB
9Elfogadva4/46ms4916 KiB
10Elfogadva4/46ms5092 KiB
11Hibás válasz0/414ms5536 KiB
12Hibás válasz0/428ms6292 KiB
13Hibás válasz0/629ms5936 KiB
14Elfogadva6/659ms6932 KiB
15Hibás válasz0/6101ms8544 KiB
16Részben helyes3/6188ms10596 KiB
17Időlimit túllépés0/6233ms12212 KiB
18Időlimit túllépés0/6287ms13488 KiB
19Időlimit túllépés0/6289ms13468 KiB
20Időlimit túllépés0/6284ms14256 KiB
21Időlimit túllépés0/6280ms14476 KiB
22Időlimit túllépés0/6287ms14700 KiB