Submission #906688

#	Time	Username	Problem	Language	Result	Execution time	Memory
906688		dsyz	Financial Report (JOI21_financial)	C++17	5 / 100	637 ms	70504 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll N,D;
ll arr[MAXN];
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll nval){
		if(s == e){
			v = nval;
			return;
		}else{
			if(x > m) r -> update(x,nval);
			else l -> update(x,nval);
			v = max(l -> v,r -> v);
		}
	}
	ll rmq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmq(x,y);
			else if(y <= m) return l -> rmq(x,y);
			else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>D;
	root = new node(0,N + 5);
	vector<ll> d;
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		d.push_back(arr[i]);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end()) - d.begin());
	for(ll i = 0;i < N;i++){
		arr[i] = lower_bound(d.begin(),d.end(),arr[i]) - d.begin();
	}
	multiset<ll> s;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	ll dp[N];
	for(ll i = 0;i < N;i++){
		dp[i] = 1;
	}
	ll ans = 0;
	for(ll i = 0;i < N;i++){
		while(!pq.empty() && pq.top().first < i){
			s.erase(s.find(pq.top().second));
			pq.pop();
		}
		ll maximum1 = 1, maximum2 = 0;
		if(!s.empty()){
			if(*s.begin() < arr[i]){
				maximum1 = max(maximum1,1 + root -> rmq(*s.begin(),arr[i] - 1));
			}
			maximum2 = max(maximum2,root -> rmq(*s.begin(),N + 5));
		}
		dp[i] = max({dp[i],maximum1,maximum2});
		root -> update(arr[i],maximum1);
		ans = max(ans,dp[i]);
		pq.push({i + D,arr[i]});
		s.insert(arr[i]);
	}
	cout<<ans<<'\n';
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35