Submission #167903

#TimeUsernameProblemLanguageResultExecution timeMemory
167903muhi1112Pismo (COCI18_pismo)C++17
0 / 70
72 ms44252 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define f1 first #define s2 second #define pb push_back #define mp make_pair #define ll long long #define fri(a) freopen(a,"r",stdin); #define fro(a) freopen(a,"w",stdout); const int N=1e5+5; const int INF=1e9+7; ll n,dizi[N],lok[N],maxst[N][25],tleft[N],tright[N],ans=INF; stack<int>st1,st2; void loki(){ for(int i=2;i<N;i++){ lok[i]=lok[i/2]+1; } return; } void build(){ for(int j=1;j<25;j++){ for(int i=0;i+(1<<j)<N;i++){ maxst[i][j]=max(maxst[i][j-1],maxst[i+(1<<(j-1))][j-1]); } } return; } ll qmax(int l,int r){ int j=lok[(r-l+1)]; return max(maxst[l][j],maxst[r-(1<<j)+1][j]); } void prepro1(){ for(int i=0;i<=n;i++){ while(!st1.empty() && dizi[i]<=dizi[st1.top()]){ st1.pop(); } tleft[i]=st1.top()+1; st1.push(i); } while(!st1.empty()){ st1.pop(); } return; //cout<<endl; } void prepro2(){ for(int i=n+1;i>0;i--){ while(!st1.empty() && dizi[i]<=dizi[st1.top()]){ st1.pop(); } tright[i]=st1.top()-1; st1.push(i); } return; } ll solve(){ for(int i=1;i<=n;i++){ //cout<<tright[i]<<" "<<tleft[i]<<" "<<qmax(tright[i],tleft[i])<<endl; ans=min(ans,tright[i]-tleft[i]>0?qmax(tleft[i],tright[i])-dizi[i]:INF); } return ans; } int main(){ //fri("in.txt"); //fro("out.txt"); ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; memset(dizi,-1,sizeof(dizi)); for(int i=1;i<=n;i++){ cin>>dizi[i]; maxst[i][0]=dizi[i]; } loki(); build(); //cout<<qmax(2,2); prepro1(); prepro2(); //cout<<tleft[5]<<" "<<tright[5]<<endl; cout<<solve()<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...