Submission #914651

#	Time	Username	Problem	Language	Result	Execution time	Memory
914651		elotelo966	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	2 ms	6492 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]=max(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]=max(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 max(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 max(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];
	int tut=dizi[1];
	for(int i=2;i<=n;i++){
		tut=max(tut+1,dizi[i]);
		pre[i]=tut-dizi[i];
	}
	tut=dizi[n];
	for(int i=n-1;i>=1;i--){
		tut=max(tut+1,dizi[i]);
		suf[i]=tut-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<<cev<<'\n';
	return 0;
}

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