Submission #470433

#	Time	Username	Problem	Language	Result	Execution time	Memory
470433		sinamhdv	LIS (INOI20_lis)	C++11	100 / 100	2601 ms	222236 KiB

Main

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 1000100;
const int LOGN = 25;

int n;
int qp[MAXN], qx[MAXN];
int fen[MAXN];
int pos[MAXN];
int val[MAXN];
set<int> apos[MAXN], dppos[MAXN];
int dp[MAXN];
int ans = 0;

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

inline int fenbs(int x)
{
	int sum = 0, ptr = 0;
	for (int i = LOGN - 1; i >= 0; i--)
	{
		int nd = ptr + (1 << i);
		if (nd < MAXN - 5 && sum + fen[nd] < x) sum += fen[nd], ptr = nd;
	}
	return ptr;
}

void updatedp(int v)
{
	ans = max(ans, dp[v]);

	auto it = dppos[dp[v]].upper_bound(v);
	vector<set<int>::iterator> vec;
	while (it != dppos[dp[v]].end() && val[*it] > val[v])
		vec.pb(it), it++;
	for (auto it : vec)
	{
		int u = *it;
		dppos[dp[v]].erase(it);
		dppos[dp[v] + 1].insert(u);
		dp[u]++;
		updatedp(u);
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n;
	FOR(i, 0, n) cin >> qp[i] >> qx[i];
	FOR(i, 0, n) add(i, 1);
	for (int i = n - 1; i >= 0; i--)
	{
		pos[i] = fenbs(qp[i]);
		add(pos[i], -1);
		val[pos[i]] = qx[i];
	}

	dbgr(pos, pos + n);
	dbgr(val, val + n);

	FOR(i, 0, n)
	{
		int x = qx[i], p = pos[i];
		for (int j = x - 1; j >= 0; j--)
		{
			auto it = apos[j].lower_bound(p);
			if (it == apos[j].begin()) continue;
			it--;
			dp[p] = max(dp[p], dp[*it]);
		}
		dp[p]++;

		apos[x].insert(p);
		dppos[dp[p]].insert(p);
		updatedp(p);

		dbgr(dp, dp + n);

		cout << ans << endl;
	}

	return 0;
}

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