Submission #530651

#	Time	Username	Problem	Language	Result	Execution time	Memory
530651		huangqr	Financial Report (JOI21_financial)	C++14	100 / 100	990 ms	65808 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld,ld> pd;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
const ll lim=3e5+5,mod=1e9+7;
ll par[lim],a[lim],dp[lim]; //Calced vals can be updated later. In a strict DP sense it would be dp(pos, time) rather than just dp(pos)

ll fs(ll x){
	if(x==par[x])return x;
	else return par[x]=fs(par[x]);
}

void mergeset(ll a,ll b){
	a=fs(a),b=fs(b);
	if(a==b)return;
	par[a]=b;
}

struct node{
	ll s,e,m,v=0,tomaxify=0;
	bool lazyflag=0,active=0;
	node *l,*r;
	node(ll ss,ll ee){
		s=ss,e=ee,m=(s+e)/2;
		if(s==e)l=r=NULL;
		else l=new node(s,m),r=new node(m+1,e);
	}
	ll push(){
		if(!active){
			tomaxify=lazyflag=0;
			return v;
		}
		if(lazyflag){
			v=max(v,tomaxify);
			if(s!=e){
				if(l->active){
					l->lazyflag=1;
					l->tomaxify=max(l->tomaxify,tomaxify);
				}
				if(r->active){
					r->lazyflag=1;
					r->tomaxify=max(r->tomaxify,tomaxify);
				}
			}
			lazyflag=0;
			tomaxify=0;
		}
		return v;
	}
	void activate(ll pos,ll dpv){
		push();
		active=1;
		if(s==e&&s==pos)v=dpv;
		else if(pos<=m)l->activate(pos,dpv);
		else r->activate(pos,dpv);
		if(s!=e){
			v=max(l->v,r->v);
		}
	}
	void maxify(ll a,ll b,ll maxifyval){
		push();
		if(!active)return;
		if(s==a&&e==b){
			lazyflag=1;
			tomaxify=maxifyval;
			push();
		}
		else if(b<=m)l->maxify(a,b,maxifyval);
		else if(a>m)r->maxify(a,b,maxifyval);
		else l->maxify(a,m,maxifyval),r->maxify(m+1,b,maxifyval);
		if(s!=e){
			push();
			v=max(l->push(),r->push());
		}
	}
	ll query(ll a,ll b){
		if(!active)return 0;
		push();
		if(s==a&&e==b)return v;
		else if(b<=m)return l->query(a,b);
		else if(a>m)return r->query(a,b);
		else return max(l->query(a,m),r->query(m+1,b));
	}
}*root;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	ll n,d;
	cin>>n>>d;
	vector<pl>v;
	root=new node(0,n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		par[i]=i;
		v.emplace_back(a[i],-i);
	}
	sort(v.begin(),v.end());
	for(auto p:v){
		ll i=-p.second;
		
		//dp[i]=max(1ll,dp[i]);
		//for(int j=max(i-d,0ll);j<i;j++)dp[i]=max(dp[i],dp[j]+1);
		if(i>0)dp[i]=1+root->query(max(i-d,0ll),i-1);
		else dp[i]=1;
		root->activate(i,dp[i]);
		
		ll t = fs(i); //t is the rightmost node to which we can push a dp-val update
		while(t < min(i+d,n-1)){
			mergeset(t, t+1);
			t = fs(t);
		}
		
		if(i<n-1)root->maxify(i+1,t,dp[i]);
		//for(int j=i+1;j<=t;j++){
		//	if(dp[j])dp[j]=max(dp[j],dp[i]);
		//}
		
		//cout<<"after "<<i<<" (val "<<p.first<<"):\n";
		//for(int i=0;i<n;i++)cout<<dp[i]<<" ";
		//cout<<"\n";
	}
	
	cout<<root->query(n-1,n-1);
	
	return 0;
}

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