Submission #999537

#	Time	Username	Problem	Language	Result	Execution time	Memory
999537		aykhn	LIS (INOI20_lis)	C++17	100 / 100	1861 ms	135508 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

struct DSU
{
	vector<int> e;
	void init(int n)
	{
		e.assign(n + 1, -1);
	}
	int get(int x)
	{
		if (e[x] < 0) return x;
		return e[x] = get(e[x]);
	}
	void unite(int x, int y)
	{
		x = get(x), y = get(y);
		if (x == y) return;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
	}
};
struct BIT
{
	int n;
	vector<int> ft;
	void init(int N)
	{
		n = N + 5;
		ft.assign(n + 5, 0);
	}
	void add(int pos, int val)
	{
		for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
 	}
	int get(int pos, int res = 0)
	{
		for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
		return res;
	}
};

const int MXN = 1e6 + 5;

set<int> st[MXN];
int res[MXN], v[MXN];
int ans = 0;

void add(int i)
{
	ans = max(ans, res[i]);
	auto it = st[res[i]].begin();
	while ((it = st[res[i]].upper_bound(i)) != st[res[i]].end() && v[*it] > v[i])
	{
		int x = *it;
		st[res[i]].erase(it);
		res[x] = res[i] + 1;
		add(x);
	}
	st[res[i]].insert(i);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	array<int, 2> a[n];
	for (array<int, 2> &i : a) cin >> i[0] >> i[1];
	BIT ft;
	ft.init(n);
	for (int i = n - 1; i >= 0; i--)
	{
		int l = 1, r = n;
		while (l < r)
		{
			int mid = (l + r) >> 1;
			if (mid - ft.get(mid) >= a[i][0]) r = mid;
			else l = mid + 1;
		}
		a[i][0] = l;
		v[l] = a[i][1];
		ft.add(l, 1);
	}
	for (array<int, 2> &i : a)
	{
		res[i[0]] = 1;
		for (int j = 1; j < i[1]; j++)
		{
			auto it = st[j].lower_bound(i[0]);
			if (!(it == st[j].begin() || v[*prev(it)] >= i[1])) res[i[0]] = j + 1;
		}
		add(i[0]);
		cout << ans << '\n';
	}
}

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