Submission #635831

#	Time	Username	Problem	Language	Result	Execution time	Memory
635831		S2speed	LIS (INOI20_lis)	C++17	100 / 100	624 ms	74344 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 1e6 + 17 , maxa = 1.5e3 , inf = 2e16;

struct segtree {

	ll sz = 1;
	vector<ll> val;

	void build(ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = 1;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(ln , lx , m); build(rn , m , rx);
		val[x] = val[ln] + val[rn];
		return;
	}

	void build(){
		build(0 , 0 , sz);
		return;
	}

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.resize(sz << 1);
		build();
		return;
	}

	void set(ll i , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = 0;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			set(i , ln , lx , m);
		} else {
			set(i , rn , m , rx);
		}
		val[x] = val[ln] + val[rn];
		return;
	}

	void set(ll i){
		set(i , 0 , 0 , sz);
		return;
	}

	ll cal(ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			return lx;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(val[ln] >= k){
			return cal(k , ln , lx , m);
		}
		return cal(k - val[ln] , rn , m , rx);
	}

	ll cal(ll k){
		ll h = cal(k , 0 , 0 , sz);
		set(h);
		return h;
	}

};

struct mintree {

	ll sz = 1;
	vector<ll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , inf);
		return;
	}

	void set(ll i , ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = min(val[x] , k);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			set(i , k , ln , lx , m);
		} else {
			set(i , k , rn , m , rx);
		}
		val[x] = min(val[ln] , val[rn]);
		return;
	}

	void set(ll i , ll k){
		set(i , k , 0 , 0 , sz);
		return;
	}

	ll cal(ll l , ll r , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return inf;
		if(rx <= r && lx >= l) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		ll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return min(a , b);
	}

	ll cal(ll l , ll r){
		return cal(l , r , 0 , 0 , sz);
	}

};

segtree st;
mintree mt[maxa];
ll t[maxn] , a[maxn] , p[maxn] , x[maxn] , ans[maxn];
vector<ll> v;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n;
	cin>>n;
	for(ll i = 0 ; i < n ; i++){
		cin>>p[i]>>x[i];
		v.push_back(x[i]);
	}
	sort(all(v));
	v.resize(distance(v.begin() , unique(all(v))));
	st.init(n);
	for(ll i = n - 1 ; ~i ; i--){
		ll j = st.cal(p[i]);
		t[j] = i;
		a[j] = lower_bound(all(v) , x[i]) - v.begin() + 1;
	}
	ll vs = sze(v);
	for(ll i = 1 ; i <= vs ; i++){
		mt[i].init(vs + 1);
	}
	for(ll i = 0 ; i < n ; i++){
		mt[1].set(a[i] , t[i]);
		for(ll j = 2 ; j <= a[i] ; j++){
			ll h = max(t[i] , mt[j - 1].cal(0 , a[i]));
			mt[j].set(a[i] , h);
		}
	}
	for(ll j = 1 ; j <= vs ; j++){
		ll h = mt[j].cal(0 , vs + 1);
		if(h == inf) break;
		ans[h] = j;
	}
	cout<<"1\n";
	for(ll i = 1 ; i < n ; i++){
		ans[i] = max(ans[i] , ans[i - 1]);
		cout<<ans[i]<<'\n';
	}
	return 0;
}

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