Submission #1257147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257147		mhn_neek	LIS (INOI20_lis)	C++20	20 / 100	4108 ms	329356 KiB

Main

//In the name of God
#include<bits/stdc++.h>
/*MHN*/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T> 
using ordered_set = tree<    T,    null_type,    less<T>,    rb_tree_tag,    tree_order_statistics_node_update>;
typedef  int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=1e6+10;
const lli mod=1e9+7;//998244353;//1e9+9
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
struct Fenwick{
	ve bit;
	lli n;
	void build(lli sz){
		FOR(i,sz)bit.PB(0);
		n = sz;
	}
	void update(lli i,lli x){
		if(i == 0){bit[0] = max(bit[0],x);return;}
		for(; i <= n; i += i&(-i))
			bit[i] = max(bit[i],x);
	}
	lli get(lli i){
		lli ans = bit[0];
		for(; i > 0; i -= (-i)&i)
			ans = max(ans,bit[i]);
		return ans;
	}
};

lli n;
pii Q[N];
lli pos[N],A[N],dp[N];



struct Node{
	ve ozv;
	Fenwick fen;
};
Node seg[N*4];
Node DEF;
Node Merge(Node a,Node b){
	Node res;
	for(auto i : a.ozv)res.ozv.PB(i);
	for(auto i : b.ozv)res.ozv.PB(i);
	sort(all(res.ozv));
	return res;
}

Node Tak(lli p){
	Node res;
	res.ozv.PB(A[p]);
	res.fen.build(1);
	return res;
}
void build(lli l = 1,lli r = n+1,lli id = 1){
	if(r-l == 1){
		seg[id] = Tak(l);
		return;
	}
	lli mid = (l+r)/2;
	build(l,mid,id*2);
	build(mid,r,id*2+1);
	seg[id] = Merge(seg[id*2],seg[id*2+1]);
	seg[id].fen.build(seg[id].ozv.size());
}
void Upd(lli l,lli r,lli p,lli id){
	if(r<=p || l>p)return;
	lli in = lb(all(seg[id].ozv),A[p]) - seg[id].ozv.begin();
	seg[id].fen.update(in,dp[p]);
	if(r-l == 1){
		return;
	}
	lli mid = (l+r)/2;
	Upd(l,mid,p,id*2);
	Upd(mid,r,p,id*2+1);
}
lli Get(lli l,lli r,lli st,lli en,lli num,lli id){
	if(l >= en || r <= st)return 0;
	if(l>=st && r<=en){
		lli in = lb(all(seg[id].ozv),num) - seg[id].ozv.begin();
		in --;
		if(in >= 0)return seg[id].fen.get(in);
		return 0;
	}
	lli mid = (l+r)/2;
	lli res = max(Get(l,mid,st,en,num,id*2) ,Get(mid,r,st,en,num,id*2+1) );
	return res;
}

ve mak[N],rmak[N];
bool came[N];

void input(){
	cin>>n;
	ordered_set<lli> mos;
	FORS(i,n){
		cin>>Q[i].fi>>Q[i].se;
		mos.insert(i);
	}
	for(lli i = n; i > 0; i --){
		pos[i] = *mos.find_by_order(Q[i].fi-1);
		A[pos[i]] =  Q[i].se;
		mak[Q[i].se].PB(pos[i]);
		for(lli j = Q[i].se; j > 0; j--)
			rmak[j].PB(pos[i]);
		mos.erase(mos.find(pos[i]));
	}
	FOR(i,N)sort(all(mak[i]));
	FOR(i,N)sort(all(rmak[i]));
}

int main(){
    migmig;
	input();
	build();
		lli ans = 0;
	FORS(i,n){
		lli in = Q[i].fi,x = Q[i].se;
		in = pos[i];
		came[in] =1;
		dp[in]=1;
		for(lli j = x-1; j > 0 ; j--){
			for(auto k : mak[j]){
				if(k >  in)continue;
				dp[in] = max(dp[in],dp[k] + 1);
				ans=max(ans,dp[k]);
			}
		}
		Upd(1,n+1,in,1);
		for(auto j : rmak[x+1]){
			if(came[j] == 0)continue;
			lli la = dp[j];
			dp[j] = max(dp[j],1+Get(1,n+1,1,j,A[j],1));
			ans=max(ans,dp[j]);
			if(dp[j] != la)
				Upd(1,n+1,j,1);
		}
		ans = max(ans,dp[in]);
		cout<<ans<<endl;
		
	}
	


}

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