Submission #1256732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256732		pasta	LIS (INOI20_lis)	C++20	100 / 100	1308 ms	112044 KiB

Main

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

#define pb	push_back
#define all(x) 	(x).begin(), (x).end()
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define S	second
#define F   first
#define lc	(id * 2)
#define rc	(lc + 1)


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

const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
const int LOG = 23;

int n, fen[maxn], p[maxn], x[maxn], q[maxn], ans;
set<int> mem[maxn];

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

int get(int x) {
	int pos = 0;
	for (int i = LOG - 1; i >= 0; i--) {
		if (pos + (1 << i) <= n && fen[pos + (1 << i)] < x) {
			pos += (1 << i);
			x -= fen[pos];
		}
	}
	return pos + 1;
}

void update(pii src) {
	queue<pii> qe;
	qe.push(src);
	while (!qe.empty()) {
		auto [i, ln] = qe.front();
		qe.pop();
		ans = max(ans, ln);

		while (!mem[ln].empty()) {
			auto nw = mem[ln].lower_bound(i);
			if (nw == mem[ln].end())
				break;
			// cout << q[i] << '\n';
			if (x[q[(*nw)]] <= x[q[i]])
				break;
			mem[ln].erase(nw);
			qe.push({*nw, ln + 1});
		}
		mem[ln].insert(i);
	}
}


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

	for (int i = n; i >= 1; i--) {
		int j = get(p[i]);
		p[i] = j;
		q[j] = i;
		add(j, -1);
	}

	mem[0].insert(0);
	for (int i = 1; i <= n; i++) {
		int cur = 0;
		while (!mem[cur].empty()) {
			auto nw = mem[cur].lower_bound(p[i]);
			if (nw == mem[cur].begin())
				break;
			nw = prev(nw);
			if (x[q[*nw]] >= x[i])
				break;
			cur++;
		}
		update({p[i], cur});
		cout << ans << '\n';
	}
}

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