Submission #1292309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292309		lmduc270410	LIS (INOI20_lis)	C++20	20 / 100	4091 ms	944 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

int q;
vector<int> vc;
int d[N], k;
int lis(vector<int> v){
	k = 0;
	for(int x : v){
		int j = lower_bound(d + 1, d + k + 1, x) - d;
		if(j > k) d[++k] = x;
		else d[j] = x;
	}
	return k;
}

void solve(){
	
	cin>>q;
	while(q--){
		int p, x; cin>>p>>x;
		vector<int> st;
		while((int)vc.size() >= p){
			st.push_back(vc.back());
			vc.pop_back();
		}
		vc.push_back(x);
		while(!st.empty()){
			vc.push_back(st.back());
			st.pop_back();
		}
		cout<<lis(vc)<<'\n';
	}
}

signed main(){
	
	// freopen(".inp", "r", stdin);
	// freopen(".out", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int tc = 1;
	// cin>>tc;
	while(tc--) solve();
}

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