#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
71 ms |
39928 KB |
Output isn't correct |
| 2 |
Correct |
75 ms |
39928 KB |
Output is correct |
| 3 |
Correct |
81 ms |
39928 KB |
Output is correct |
| 4 |
Correct |
75 ms |
39800 KB |
Output is correct |
| 5 |
Incorrect |
969 ms |
40184 KB |
Output isn't correct |
| 6 |
Incorrect |
985 ms |
40184 KB |
Output isn't correct |
| 7 |
Incorrect |
977 ms |
40280 KB |
Output isn't correct |
