Submission #469249

#	Time	Username	Problem	Language	Result	Execution time	Memory
469249		Millad	LIS (INOI20_lis)	C++14	20 / 100	4066 ms	116116 KiB

Main

/// In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << '\n'
     
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pll;
     
const ll maxn = 1e6 + 5;

ll q, x[maxn], p[maxn], b[maxn], ind[maxn],fen[maxn], dp[maxn], lis, pw2[25];
set <ll> A[maxn], B[maxn];
vector <ll> Qu;
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	pw2[0] = 1;
	for(ll i = 1; i < 22; i ++)pw2[i] = (pw2[i - 1] * 2ll);
	cin >> q;
	for(ll i = 1; i <= q; i ++){
		cin >> p[i] >> x[i];
		for(ll j = i; j <= q; j += (j & (-j)))
			fen[j] ++;
	}
	for(ll i = q; i; i --){
		ll sum = 0, cur = 0;
		for(ll j = 19; j >= 0; j --){
			if(cur + pw2[j] > q)continue;
			if(sum + fen[cur + pw2[j]] < p[i]){
				cur += pw2[j];
				sum += fen[cur];
			}
		}
		ind[i - 1] = cur;
		b[cur] = x[i];
		cur ++;
		for(; cur < q; cur += (cur & (-cur)))fen[cur] --;
	}
	set<ll>::iterator pnt;
	for(ll i = 0; i < q; i ++){
		ll id = ind[i], d = 1;
		A[b[id]].insert(id);;
		for(ll j = 1; j < b[id]; j ++){
			if(A[j].empty())continue;
			if(*A[j].begin() > id)continue;
			pnt = A[j].upper_bound(id);
			pnt --; d = max(d, dp[*pnt] + 1);
		}
		dp[id] = d; B[d].insert(id);
		Qu.pb(id); lis = max(lis, d);
		while(Qu.size()){
			ll id2 = Qu.back(); Qu.pop_back();
			pnt = B[dp[id2]].lower_bound(id2);
			vector <ll> vec;
			while(true){
				pnt ++;
				if(pnt == B[dp[id2]].end())break;
				if(b[*pnt] < b[id2])break;
				if(b[*pnt] == b[id2])continue;
				vec.pb(*pnt);
			}
			for(ll j : vec){
				B[dp[j]].erase(j);
				dp[j] ++; lis = max(lis, dp[j]);
				B[dp[j]].insert(j); Qu.pb(j); 
			}
		}
		cout << lis << '\n';
	}
}	

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