Submission #469002

#	Time	Username	Problem	Language	Result	Execution time	Memory
469002		Millad	LIS (INOI20_lis)	C++14	20 / 100	330 ms	936 KiB

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 / 20
• Subtask 2: 0 / 80