# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
167898 | muhi1112 | Pismo (COCI18_pismo) | C++17 | 764 ms | 40312 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
int n,dizi[N],lok[N],a,b,c,d,ans1=INF,cnt;
pair<int,int>minst[N][25],maxst[N][25];
void loki(){
for(int i=2;i<N;i++){
lok[i]=lok[i/2]+1;
}
}
void build(){
for(int j=1;j<25;j++){
for(int i=0;i+(1<<j)<N;i++){
minst[i][j]=min(minst[i][j-1],minst[i+(1<<(j-1))][j-1]);
maxst[i][j]=max(maxst[i][j-1],maxst[i+(1<<(j-1))][j-1]);
}
}
}
pair<int,int> qmax(int l,int r){
int j=lok[(r-l+1)];
return max(maxst[l][j],maxst[r-(1<<j)+1][j]);
}
pair<int,int> qmin(int l,int r){
int j=lok[(r-l+1)];
return min(minst[l][j],minst[r-(1<<j)+1][j]);
}
int solve(int l,int r){
cnt++;
if(l>=r){
return INF;
}
pair<int,int> mini=qmin(l,r);
pair<int,int> maxi=qmax(l,r);
//cout<<l<<" "<<r<<" "<<mini.s2<<" "<<maxi.s2<<endl;
int ans=INF;
ans=min(ans,maxi.f1-mini.f1);
ans=min(solve(l,mini.s2-1),ans);
ans=min(solve(mini.s2+1,r),ans);
ans=min(solve(l,maxi.s2-1),ans);
ans=min(solve(maxi.s2+1,r),ans);
ans1=min(ans,ans1);
if(cnt>=150000000){
cout<<ans1<<endl;
exit(0);
}
return ans;
}
int main(){
//fri("in.txt");
//fro("out.txt");
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i=0;i<n;i++){
cin>>dizi[i];
minst[i][0]={dizi[i],i};
maxst[i][0]={dizi[i],i};
}
loki();
build();
//cout<<qmax(1,2).f1<<" "<<qmax(1,2).s2<<endl;
cout<<solve(0,n-1)<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |