fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct quer { int l,r,pos; };
  4. const int MAXN=3e5+5;
  5. const int INF=1e9;
  6. const int sqr=400;
  7. int nex[MAXN],prv[MAXN],num[MAXN],pos[MAXN],V[MAXN],ans[MAXN],dp[sqr+5][MAXN],f[MAXN];
  8. map<int,int> mp;
  9. vector<quer> vi[MAXN/sqr+5];
  10. int n,q;
  11. bool sortq(quer a,quer b) { return a.r>b.r; }
  12. int add(int x)
  13. {
  14.     int ans=INF;
  15.     if(prv[x]>=1) ans=min(ans,V[x]-V[prv[x]]);
  16.     if(nex[x]<=n) ans=min(ans,V[nex[x]]-V[x]);
  17.     nex[prv[x]]=x,prv[nex[x]]=x;
  18.     return ans;
  19. }
  20. void del(int x) { nex[prv[x]]=nex[x],prv[nex[x]]=prv[x]; }
  21. int main()
  22. {
  23.     ios::sync_with_stdio(0);
  24.     cin.tie(0);
  25.     cout.tie(0);
  26.     cin>>n;
  27.     for(int i=1;i<=n;i++) { cin>>num[i];V[i]=num[i]; }
  28.     sort(V+1,V+n+1);
  29.     V[0]=-INF,V[n+1]=INF*2;
  30.     for(int i=1;i<=n;i++) pos[i]=lower_bound(V+1,V+n+1,num[i])-V+(mp[lower_bound(V+1,V+n+1,num[i])-V]++);
  31.     cin>>q;
  32.     for(int i=1;i<=q;i++) { int l,r;cin>>l>>r;vi[(l-1)/sqr].push_back({l,r,i}); }
  33.     for(int i=0;i<=n/sqr;i++) sort(vi[i].begin(),vi[i].end(),sortq);
  34.     for(int i=1;i<=min(sqr,n);i++)
  35.     {
  36.         if(i==1) { for(int j=1;j<=n;j++) dp[i][j]=INF; }
  37.         else for(int j=1;j<=n-i+1;j++) dp[i][j]=min(min(dp[i-1][j],dp[i-1][j+1]),abs(num[j]-num[j+i-1]));
  38.     }
  39.     for(int i=0;i*sqr<=n;i++)
  40.     {
  41.         int l=i*sqr+1,r=min(n,(i+1)*sqr),p=n;
  42.         f[r]=INF;
  43.         for(int j=0;j<=n+1;j++) prv[j]=j-1,nex[j]=j+1;
  44.         for(int j=1;j<r;j++) del(pos[j]);
  45.         for(int j=n;j>r;j--) del(pos[j]);
  46.         for(int j=r+1;j<=n;j++) f[j]=min(f[j-1],add(pos[j]));
  47.         for(int j=r-1;j>=l;j--) add(pos[j]);
  48.         for(auto v:vi[i])
  49.         {
  50.             if(v.r-v.l+1<=sqr) { ans[v.pos]=dp[v.r-v.l+1][v.l];continue; }
  51.             ans[v.pos]=f[v.r];
  52.             while(p>v.r) del(pos[p--]);
  53.             for(int j=l;j<r;j++) del(pos[j]);
  54.             for(int j=r-1;j>=v.l;j--) ans[v.pos]=min(ans[v.pos],add(pos[j]));
  55.             for(int j=v.l-1;j>=l;j--) add(pos[j]);
  56.         }
  57.     }
  58.     for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
  59. }
Success #stdin #stdout 0.01s 7828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3AZI7F
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!