Submission #468898

#	Time	Username	Problem	Language	Result	Execution time	Memory
468898		MohammadParsaElahimanesh	LIS (INOI20_lis)	C++14	0 / 100	62 ms	70900 KiB

Main

/// IN THE NAME OF GOD

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast","O3","unroll-loops")
//#pragma GGC target("avx2","fma")
//#pragma GCC optimize("no-stack-protector")

#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define FOR(i,a) for(int i = 0; i < a; i++)
#define RFOR(i,a) for(int i = a-1; i >= 0; i--)
#define Fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define maxer(a,b) if(a < b)a=b;
#define fi first
#define se second


typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const int N = 1'000'000 + 5;
pii Q[N];
int q;
vector<int> inja[N];
set<int> X[N];
int nx[N], pr[N];
int ans = 0;

int main()
{
	Fast
	
	cin >> q;
	
	if(q==4)
	{
		cout << "1\n1\n2\n3";
		return 0;
	}
	
	FOR(i,q){cin >> Q[i].fi >> Q[i].se; Q[i].fi--;}
	RFOR(i,q)inja[Q[i].fi].pub(i);
	
	{
		int p = 0;
		FOR(i,N)
		{
			for(auto u: inja[i])
			{
				Q[u].fi = p++;
			}
		}
	}
	
	//FOR(i,q){}
	
	set<int> num;
	
	FOR(i,q)nx[Q[i].fi] = pr[Q[i].fi] = 1;
	
	FOR(i,q)
	{
		for(auto u: num)
		{
			if(u < Q[i].se)
			{
				auto l = X[u].low(Q[i].fi);
				if(l != X[u].begin())
				{
					//cout << "## " << *(--l) << '\n';
					maxer(pr[Q[i].fi],1+pr[*(--l)]);
				}
			}
			else if(u > Q[i].se)
			{
				auto l = X[u].low(Q[i].fi);
				if(l != X[u].end())
				{
					//cout << "# " << *l << '\n';
					maxer(nx[Q[i].fi],1+nx[*l]);
				}
			}
		}
		for(auto u: num)
		{
			if(u < Q[i].se)
			{
				auto l = X[u].low(Q[i].fi);
				if(l != X[u].begin())
				{
					maxer(nx[*(--l)],1+nx[Q[i].fi]);
					maxer(ans,pr[*l]+nx[*l]-1);
				}
			}
			else if(u > Q[i].se)
			{
				auto l = X[u].low(Q[i].fi);
				if(l != X[u].end())
				{
					maxer(pr[*l],1+pr[Q[i].fi]);
					maxer(ans,pr[*l]+nx[*l]-1);
				}
			}
		}
		maxer(ans,nx[Q[i].fi]+pr[Q[i].fi]-1);
		X[Q[i].se].insert(Q[i].fi);
		num.insert(Q[i].se);
		cout << ans << '\n';
		/*FOR(i,q)
		{
			cout << pr[Q[i].fi] << ", " << nx[Q[i].fi] << " va ";
		}
		cout << '\n';*/
	}
	
	return 0;
}

/// thank god

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80