Submission #1156698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156698		alexander707070	Financial Report (JOI21_financial)	C++20	100 / 100	1614 ms	24572 KiB

Main

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

bool cmp(pair<int,int> fr,pair<int,int> sc){
	if(fr.first!=sc.first)return fr.first<sc.first;
	return fr.second>sc.second;
}

struct SegmentTree{
	struct node{
		int len,ans,pref,suff;

		inline friend node operator + (node fr,node sc){
			node res={0,0,0,0};
			
			res.len=fr.len+sc.len;
			res.ans=max(max(fr.ans,sc.ans),fr.suff+sc.pref);

			if(fr.len==fr.pref)res.pref=fr.len+sc.pref;
			else res.pref=fr.pref;

			if(sc.len==sc.suff)res.suff=fr.suff+sc.len;
			else res.suff=sc.suff;

			return res;
		}
	};

	node tree[4*MAXN];

	void build(int v,int l,int r){
		if(l==r)tree[v]={1,1,1,1};
		else{
			int tt=(l+r)/2;
			build(2*v,l,tt);
			build(2*v+1,tt+1,r);

			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}

	void update(int v,int l,int r,int pos){
		if(l==r){
			tree[v]={1,0,0,0};
		}else{
			int tt=(l+r)/2;
			if(pos<=tt)update(2*v,l,tt,pos);
			else update(2*v+1,tt+1,r,pos);

			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}

	node info(int v,int l,int r,int ll,int rr){
		if(ll>rr)return {0,0,0,0};
		if(l==ll and r==rr)return tree[v];

		int tt=(l+r)/2;
		return info(2*v,l,tt,ll,min(tt,rr)) + info(2*v+1,tt+1,r,max(tt+1,ll),rr);
	}
}seg;

struct ST{
	int tree[4*MAXN];

	void update(int v,int l,int r,int pos,int val){
		if(l==r){
			tree[v]=val;
		}else{
			int tt=(l+r)/2;
			if(pos<=tt)update(2*v,l,tt,pos,val);
			else update(2*v+1,tt+1,r,pos,val);

			tree[v]=max(tree[2*v],tree[2*v+1]);
		}
	}

	int getmax(int v,int l,int r,int ll,int rr){
		if(ll>rr)return 0;
		if(l==ll and r==rr)return tree[v];

		int tt=(l+r)/2;
		return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
	}
}segdp;

int n,d;
int dp[MAXN];
pair<int,int> p[MAXN];
bool used[MAXN];

int main(){

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

	cin>>n>>d;

	for(int i=1;i<=n;i++){
		cin>>p[i].first;
		p[i].second=i;
	}

	sort(p+1,p+n+1,cmp);
	p[n+1].second=n+1;

	seg.build(1,1,n+1);

	for(int i=1;i<=n+1;i++){
		int curr=p[i].second;

		seg.update(1,1,n+1,curr);

		int l=0,r=curr,tt;

		while(l+1<r){
			int tt=(l+r)/2;

			if(seg.info(1,1,n+1,tt,curr-1).ans<d){
				r=tt;
			}else{
				l=tt;
			}
		}

		dp[curr]=segdp.getmax(1,1,n+1,r,curr)+1;
		segdp.update(1,1,n+1,curr,dp[curr]);
	}

	cout<<dp[n+1]-1<<"\n";

	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