제출 #914684

#제출 시각아이디문제언어결과실행 시간메모리
914684elotelo966Growing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
51 ms17564 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...