Submission #627149

#	Time	Username	Problem	Language	Result	Execution time	Memory
627149		NothingXD	LIS (INOI20_lis)	C++14	100 / 100	1883 ms	120520 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int MAXN = 1e6 + 10;
const int LOG = 20;
int n, f[MAXN], a[MAXN], x[MAXN], Q[MAXN];
set<int> st[MAXN];

void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int find(int x){
	int idx = 0;
	for (int i = LOG-1; ~i; i--){
		if (idx + (1 << i) <= n && f[idx + (1 << i)] < x){
			idx += (1 << i);
			x -= f[idx];
		}
	}
	return idx + 1;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++){
		cin >> x[i] >> a[i];
		add(i, 1);
	}

	for (int i = n; i; i--){
		int ptr = find(x[i]);
		x[i] = ptr;
		Q[x[i]] = i;
		add(ptr, -1);
	}

	int ans = 0;
	st[0].insert(0);


	for (int i = 1; i <= n; i++){
		int cnt = 0;
		while(!st[cnt].empty()){
			auto it = st[cnt].lower_bound(x[i]);
			if (it == st[cnt].begin()) break;
			it--;
			if (a[Q[*it]] >= a[i]) break;
			cnt++;
		}
		queue<pii> q;
		q.push({x[i] , cnt});
		while(!q.empty()){
			int idx = q.front().F, ptr = q.front().S;
			q.pop();
			ans = max(ans, ptr);
			while(!st[ptr].empty()){
				auto it = st[ptr].lower_bound(idx);
				if (it == st[ptr].end()) break;
				if (a[Q[*it]] <= a[Q[idx]]) break;
				q.push({*it, ptr + 1});
				st[ptr].erase(it);
			}
			st[ptr].insert(idx);
		}
		cout << ans << '\n';
	}

}

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