Submission #999186

#	Time	Username	Problem	Language	Result	Execution time	Memory
999186		vjudge1	LIS (INOI20_lis)	C++17	20 / 100	4075 ms	26068 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;
	}
};

const int MXN = 1e6 + 5;
const int LOG = 20;

int n, S, T, A, B, b = 0;
vector<int> adj[MXN];
int p[LOG][MXN], dep[MXN], in[MXN], out[MXN], tim;
int id[MXN];

void dfs(int a)
{
	in[a] = ++tim;
	for (int &v : adj[a])
	{
		if (v == p[0][a]) continue;
		p[0][v] = a;
		dep[v] = dep[a] + 1;
		dfs(v);
	}
	out[a] = tim;
}

vector<array<int, 3>> m;

int anc(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
}
int LCA(int u, int v)
{
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (anc(p[i][u], v)) continue;
		u = p[i][u];
	}
	return p[0][u];
}
int DIST(int u, int v)
{
	return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> q;
	vector<int> v;
	for (int i = 0; i < q; i++)
	{
		int j, x;
		cin >> j >> x;
		v.insert(v.begin() + j - 1, x);
		vector<int> y;
		for (int &i : v)
		{
			if (y.empty() || i > y.back()) y.push_back(i);
			y[lower_bound(y.begin(), y.end(), i) - y.begin()] = i;
		}
		cout << y.size() << '\n';
	}
}

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