Submission #637480

#	Time	Username	Problem	Language	Result	Execution time	Memory
637480		Arinoor	LIS (INOI20_lis)	C++17	100 / 100	1592 ms	128356 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ios			ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define bug2(x, y)	cout << #x << ' ' << #y  << " : " << x << ' ' << y << endl
#define bug(x)		cout << #x << " : " << x << endl
#define all(x)		x.begin(), x.end()
#define pb			push_back
#define mp			make_pair
#define fi			first
#define se			second

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxlg = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int q, ind[maxn], a[maxn], dp[maxn], ans;
int fen[maxn];
pii Q[maxn];
set<int> S[maxn];

void add(int i, int x){
	for(; i <= q; i += i & -i)
		fen[i] += x;
}

int get(int x){
	int ind = 0;
	for(int i = maxlg - 1; ~i; i --){
		int j = ind + (1 << i);
		if(j <= q and fen[j] < x){
			ind = j;
			x -= fen[j];
		}
	}
	return ++ind;
}

void dfs(int i){
	int x = dp[i] + 1;
	while(true){
		auto it = S[x].upper_bound(i);
		if(it == S[x].end() or a[*it] <= a[i])
			break;
		dfs(*it);
	}
	S[dp[i]].erase(i);
	dp[i] = x;
	S[dp[i]].insert(i);
	ans = max(ans, x);
}

int main(){
	ios;
	cin >> q;
	for(int i = 0; i < q; i ++){
		cin >> Q[i].fi >> Q[i].se;
	}
	for(int i = 1; i <= q; i ++){
		add(i, 1);
	}
	for(int i = q - 1; ~i; i --){
		ind[i] = get(Q[i].fi);
		a[ind[i]] = Q[i].se;
		add(ind[i], -1);
	}
	for(int i = 0; i < q; i ++){
		int j = ind[i];
		dp[j] = 1;
		while(true){
			auto it = S[dp[j]].lower_bound(j);
			if(it == S[dp[j]].begin())
				break;
			it --;
			if(a[*it] < a[j])
				dp[j] ++;
			else
				break;
		}
		dp[j] --;
		dfs(j);
		cout << ans << '\n';
	}
}

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