oj.uz

Submission #999186

# Submission time Handle Problem Language Result Execution time Memory
999186 2024-06-15T07:57:02 Z vjudge1 LIS (INOI20_lis) C++17
20 / 100
 4000 ms 26068 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24668 KB Output is correct
2 Correct 5 ms 24900 KB Output is correct
3 Correct 16 ms 24960 KB Output is correct
4 Correct 18 ms 24924 KB Output is correct
5 Correct 14 ms 24924 KB Output is correct
6 Correct 18 ms 24772 KB Output is correct
7 Correct 22 ms 24948 KB Output is correct
8 Correct 20 ms 25176 KB Output is correct
9 Correct 21 ms 24936 KB Output is correct
10 Correct 21 ms 24924 KB Output is correct
11 Correct 18 ms 24924 KB Output is correct
12 Correct 17 ms 24792 KB Output is correct
13 Correct 19 ms 24924 KB Output is correct
14 Correct 19 ms 24936 KB Output is correct
15 Correct 18 ms 24924 KB Output is correct
16 Correct 21 ms 24924 KB Output is correct
17 Correct 19 ms 24952 KB Output is correct
18 Correct 18 ms 24948 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24668 KB Output is correct
2 Correct 5 ms 24900 KB Output is correct
3 Correct 16 ms 24960 KB Output is correct
4 Correct 18 ms 24924 KB Output is correct
5 Correct 14 ms 24924 KB Output is correct
6 Correct 18 ms 24772 KB Output is correct
7 Correct 22 ms 24948 KB Output is correct
8 Correct 20 ms 25176 KB Output is correct
9 Correct 21 ms 24936 KB Output is correct
10 Correct 21 ms 24924 KB Output is correct
11 Correct 18 ms 24924 KB Output is correct
12 Correct 17 ms 24792 KB Output is correct
13 Correct 19 ms 24924 KB Output is correct
14 Correct 19 ms 24936 KB Output is correct
15 Correct 18 ms 24924 KB Output is correct
16 Correct 21 ms 24924 KB Output is correct
17 Correct 19 ms 24952 KB Output is correct
18 Correct 18 ms 24948 KB Output is correct
19 Execution timed out 4075 ms 26068 KB Time limit exceeded
20 Halted 0 ms 0 KB -