Submission #468914

#	Time	Username	Problem	Language	Result	Execution time	Memory
468914		MohammadParsaElahimanesh	LIS (INOI20_lis)	C++14	20 / 100	4056 ms	47892 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;
set<int> X[N];
int nx[N], pr[N];
int ans = 0;

inline int LIS(vector<int> const& a)
{
	vector<int> LO;
	int pos, np = sz(a);
	FOR(i,np)
	{
		pos = low(all(LO), a[i]) - LO.begin();
		if(pos == sz(LO)){LO.pub(a[i]);}
		else LO[pos] = a[i];
	}
	return sz(LO);
}


int main()
{
	Fast
	
	vector<int> T;
	cin >> q;
	
	FOR(i,q)
	{
		cin >> Q[i].fi >> Q[i].se;
		T.insert(T.begin()+Q[i].fi-1,Q[i].se);
		cout << LIS(T) << '\n';
	}
	
	
	
	
	return 0;
	//vector<int> T;
	FOR(i,q)
	{
		T.insert(T.begin()+Q[i].fi-1,i);
	}
	FOR(i,sz(T))Q[T[i]].fi = i;
	
	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())
				{
					--l;
					//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())
				{
					--l;
					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())
				{
					//cout << " I'm bad : " << *l << '\n';
					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: 20 / 20
• Subtask 2: 0 / 80