Submission #466172

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
466172	2021-08-18T09:18:01 Z	sinamhdv	LIS (INOI20_lis)	C++11	20 / 100	4000 ms	4380 KB

Main

#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 FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define endl '\n'

const int MAXN = 1000100;

int n, p[MAXN], x[MAXN];
vector<int> vec;
int dp[MAXN];

inline int getlis(void)
{
	fill(dp, dp + MAXN, INF);
	dp[0] = -INF;
	for (int u : vec)
	{
		int pos = lower_bound(dp, dp + MAXN, u) - dp;
		dp[pos] = u;
	}
	int ans = lower_bound(dp, dp + MAXN, INF) - dp - 1;
	return ans;
}

int32_t main(void)
{
	fast_io;
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> p[i] >> x[i];
		p[i]--;
		vec.insert(vec.begin() + p[i], x[i]);
		cout << getlis() << endl;
	}
	return 0;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4172 KB	Output is correct
2	Correct	6 ms	4172 KB	Output is correct
3	Correct	1101 ms	4232 KB	Output is correct
4	Correct	1110 ms	4292 KB	Output is correct
5	Correct	1046 ms	4264 KB	Output is correct
6	Correct	1148 ms	4252 KB	Output is correct
7	Correct	1044 ms	4260 KB	Output is correct
8	Correct	1057 ms	4260 KB	Output is correct
9	Correct	1142 ms	4300 KB	Output is correct
10	Correct	1211 ms	4244 KB	Output is correct
11	Correct	1126 ms	4252 KB	Output is correct
12	Correct	1200 ms	4228 KB	Output is correct
13	Correct	1208 ms	4260 KB	Output is correct
14	Correct	1191 ms	4252 KB	Output is correct
15	Correct	1081 ms	4256 KB	Output is correct
16	Correct	1128 ms	4368 KB	Output is correct
17	Correct	1141 ms	4260 KB	Output is correct
18	Correct	1095 ms	4292 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4172 KB	Output is correct
2	Correct	6 ms	4172 KB	Output is correct
3	Correct	1101 ms	4232 KB	Output is correct
4	Correct	1110 ms	4292 KB	Output is correct
5	Correct	1046 ms	4264 KB	Output is correct
6	Correct	1148 ms	4252 KB	Output is correct
7	Correct	1044 ms	4260 KB	Output is correct
8	Correct	1057 ms	4260 KB	Output is correct
9	Correct	1142 ms	4300 KB	Output is correct
10	Correct	1211 ms	4244 KB	Output is correct
11	Correct	1126 ms	4252 KB	Output is correct
12	Correct	1200 ms	4228 KB	Output is correct
13	Correct	1208 ms	4260 KB	Output is correct
14	Correct	1191 ms	4252 KB	Output is correct
15	Correct	1081 ms	4256 KB	Output is correct
16	Correct	1128 ms	4368 KB	Output is correct
17	Correct	1141 ms	4260 KB	Output is correct
18	Correct	1095 ms	4292 KB	Output is correct
19	Execution timed out	4035 ms	4380 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-