Submission #492302

#	Time	Username	Problem	Language	Result	Execution time	Memory
492302		mosiashvililuka	Financial Report (JOI21_financial)	C++14	100 / 100	726 ms	18788 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[300009],dp[300009],D,pas,seg[1200009],SEG[1200009],seg2[1200009],za,l,r,z,zz,F[300009];
int se[1200009],se2[1200009];
pair <int, int> p[300009];
void pushdown(int q, int w, int rr){
	if(q!=w){
		seg2[rr*2]+=seg2[rr];
		seg2[rr*2+1]+=seg2[rr];
	}
	seg[rr]+=seg2[rr];seg2[rr]=0;
}
void upd(int q, int w, int rr){
	pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		seg2[rr]+=z;
		pushdown(q,w,rr);
		return;
	}
	upd(q,(q+w)/2,rr*2);
	upd((q+w)/2+1,w,rr*2+1);
	if(seg[rr*2+1]>=seg[rr*2]){
		seg[rr]=seg[rr*2+1];SEG[rr]=SEG[rr*2+1];
	}else{
		seg[rr]=seg[rr*2];SEG[rr]=SEG[rr*2];
	}
}
void read(int q, int w, int rr){
	pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		if(z<seg[rr]){
			z=seg[rr];zz=SEG[rr];
		}else{
			if(z==seg[rr]){
				zz=max(zz,SEG[rr]);
			}
		}
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
void UPD(int rr){
	if(rr==0) return;
	se[rr]=max(se[rr*2],se[rr*2+1]);
	UPD(rr/2);
}
void READ(int q, int w, int rr){
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		z=max(z,se[rr]);
		return;
	}
	READ(q,(q+w)/2,rr*2);
	READ((q+w)/2+1,w,rr*2+1);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>D;
	for(i=1; i<=a; i++){
		cin>>f[i];
	}
	za=1;
	while(za<a) za*=2;
	for(i=1; i<=a; i++){
		p[i].first=f[i];p[i].second=-i;
	}
	sort(p+1,p+a+1);
	//
	for(i=1; i<=a; i++){
		seg[za+i-1]=0;SEG[za+i-1]=i;
	}
	for(i=1; i<=a; i++){
		l=max(i-D+1,1);r=i;z=1;
		upd(1,za,1);
	}
	for(ii=1; ii<=a; ii++){
		i=-p[ii].second;
		if(i>D){
			l=1;r=i-D;z=0;zz=0;
			read(1,za,1);
			if(z!=D){
				F[i]=1;
			}else{
				F[i]=zz;
			}
		}else{
			F[i]=1;
		}
		l=max(i-D+1,1);r=i;z=-1;
		upd(1,za,1);
	}
	
	//
	for(ii=1; ii<=a; ii++){
		i=-p[ii].second;
		l=F[i];r=i-1;z=0;
		READ(1,za,1);
		dp[i]=z+1;
		se[za+i-1]=dp[i];
		UPD((za+i-1)/2);
	}
	for(i=1; i<=a; i++){
		pas=max(pas,dp[i]);
	}
	/*for(i=1; i<=a; i++){
		cout<<dp[i]<<" ";
	}
	cout<<"\n";*/
	cout<<pas;
	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