Submission #1262817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262817		mhn_neek	LIS (INOI20_lis)	C++17	0 / 100	25 ms	47688 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 long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=1e6+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
#define all(v) v.begin(),v.end()
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
lli n;
pii Q[N];
lli pos[N];
lli A[N];
set<lli> lis[N];

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

lli get(lli in){
	lli L = 1;
	lli ja = 0;
	while(1){
		auto x = lis[L].lb(pos[in]);
		if(x == lis[L].begin() || A[*x] >= A[pos[in]])break;
		L ++;
	}
	return L;
}

lli ans = 0;
void update(lli in,lli L){
	queue<pii> Q;
	Q.push(MP(pos[in],L));
	while(Q.size()){
		lli ja = Q.front().fi, boz = Q.front().se;
		ans = max(ans,boz);
		Q.pop();
		while(1){
			auto x = lis[boz].ub(ja);
			if(x == lis[boz].end())break;
			if(A[(*x)] <= A[ja])break;
			lli y = *x;
			lis[boz].erase(x);
			Q.push(MP(y,boz+1));
		}
		lis[boz].insert(ja);
	}
}


int main(){
    migmig;
	input();
	lis[0].insert(0);
	FORS(i,n){
		lli x = get(i);
		update(i,x);
		cout<<ans<<endl;
	}
}

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