Submission #469002

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469002	2021-08-30T11:23:08 Z	Millad	LIS (INOI20_lis)	C++14	20 / 100	330 ms	936 KB

Main

// In the name of god
#include <bits/stdc++.h>
     
#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << '\n'
     
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
     
const ll maxn = 1e5 + 5;
const ll inf = 1e18;

ll q, lis[2005];
vector <ll> vec;
ll get_lis(){
	for(ll i = 0; i < 2005; i ++)lis[i] = inf;
	ll mx = 0;
	for(ll i : vec){
		ll l = -1, r = vec.size();
		while(l != r - 1){
			ll mid = (l + r) / 2;
			if(lis[mid] >= i)r = mid;
			else l = mid;
		}
		lis[r] = i;
		mx = max(mx, r);
	}
	return mx + 1;
}
int main(){
	cin >> q;
	while(q --){
		ll p, x; cin >> p >> x;
		vector <ll> V;
		for(ll i = 0; i < p - 1; i ++)V.pb(vec[i]);
		V.pb(x);
		for(ll i = p - 1; i < (ll)vec.size(); i ++)V.pb(vec[i]);
		vec = V;
		cout << get_lis() << '\n';
	}
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	66 ms	428 KB	Output is correct
4	Correct	109 ms	424 KB	Output is correct
5	Correct	70 ms	428 KB	Output is correct
6	Correct	121 ms	436 KB	Output is correct
7	Correct	68 ms	416 KB	Output is correct
8	Correct	78 ms	408 KB	Output is correct
9	Correct	72 ms	432 KB	Output is correct
10	Correct	66 ms	424 KB	Output is correct
11	Correct	94 ms	412 KB	Output is correct
12	Correct	111 ms	524 KB	Output is correct
13	Correct	120 ms	424 KB	Output is correct
14	Correct	108 ms	408 KB	Output is correct
15	Correct	104 ms	432 KB	Output is correct
16	Correct	109 ms	420 KB	Output is correct
17	Correct	141 ms	524 KB	Output is correct
18	Correct	126 ms	416 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	66 ms	428 KB	Output is correct
4	Correct	109 ms	424 KB	Output is correct
5	Correct	70 ms	428 KB	Output is correct
6	Correct	121 ms	436 KB	Output is correct
7	Correct	68 ms	416 KB	Output is correct
8	Correct	78 ms	408 KB	Output is correct
9	Correct	72 ms	432 KB	Output is correct
10	Correct	66 ms	424 KB	Output is correct
11	Correct	94 ms	412 KB	Output is correct
12	Correct	111 ms	524 KB	Output is correct
13	Correct	120 ms	424 KB	Output is correct
14	Correct	108 ms	408 KB	Output is correct
15	Correct	104 ms	432 KB	Output is correct
16	Correct	109 ms	420 KB	Output is correct
17	Correct	141 ms	524 KB	Output is correct
18	Correct	126 ms	416 KB	Output is correct
19	Runtime error	330 ms	936 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-