Submission #914684

#	Time	Username	Problem	Language	Result	Execution time	Memory
914684		elotelo966	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	51 ms	17564 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1000000005
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
#define lim 200005
#define se second
#define fi first
int dizi[lim],pre[lim],suf[lim],treep[4*lim],trees[4*lim];
 
inline void build1(int node,int start,int end){
	if(start>end)return ;
	if(start==end){
		treep[node]=pre[start];
		return ;
	}
	build1(node*2,start,mid),build1(node*2+1,mid+1,end);
	treep[node]=(treep[node*2]+treep[node*2+1]);
	return ;
}
 
inline void build2(int node,int start,int end){
	if(start>end)return ;
	if(start==end){
		trees[node]=suf[start];
		return ;
	}
	build2(node*2,start,mid),build2(node*2+1,mid+1,end);
	trees[node]=(trees[node*2]+trees[node*2+1]);
	return ;
}
 
inline int query1(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	if(start>=l && end<=r)return treep[node];
	return (query1(node*2,start,mid,l,r)+query1(node*2+1,mid+1,end,l,r));
}
 
inline int query2(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	if(start>=l && end<=r)return trees[node];
	return (query2(node*2,start,mid,l,r)+query2(node*2+1,mid+1,end,l,r));
}
 
int32_t main(){
	faster
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>dizi[i];
	for(int i=2;i<=n;i++){
		pre[i]=max(dizi[i-1]+1,dizi[i])-dizi[i];
	}
	for(int i=n-1;i>=1;i--){
		suf[i]=max(dizi[i+1]+1,dizi[i])-dizi[i];
	}
	build1(1,1,n);
	build2(1,1,n);
	int cev=LLONG_MAX;
	for(int i=1;i<=n;i++){
		int tut1=query1(1,1,n,1,i);
		int tut2=query2(1,1,n,i,n);
		cev=min(cev,max(tut1,tut2));
		//cout<<tut1<<" "<<tut2<<endl;
	}
	cout<<cev<<'\n';
	return 0;
}

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60