fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld long double
  5. #define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. ll n, q, l, r, a[200005], rmax[200005][23], rmin[200005][23];
  7. ll get(ll l, ll r)
  8. {
  9.     ll k=__lg(r-l+1);
  10.     return max(rmax[l][k],rmax[r-(1<<k)+1][k])-min(rmin[l][k],rmin[r-(1<<k)+1][k]);
  11. }
  12. int main()
  13. {
  14.     fast;
  15.     cin>>n>>q;
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.         cin>>a[i];
  19.         rmin[i][0]=a[i];
  20.         rmax[i][0]=a[i];
  21.     }
  22.     for(int j=1;j<=18;j++)
  23.     {
  24.         for(int i=1;i<=n-(1<<j)+1;i++)
  25.         {
  26.             rmin[i][j]=min(rmin[i][j-1],rmin[i+(1<<(j-1))][j-1]);
  27.         }
  28.     }
  29.     for(int j=1;j<=18;j++)
  30.     {
  31.         for(int i=1;i<=n-(1<<j)+1;i++)
  32.         {
  33.             rmax[i][j]=max(rmax[i][j-1],rmax[i+(1<<(j-1))][j-1]);
  34.         }
  35.     }
  36.     while(q--)
  37.     {
  38.         cin>>l>>r;
  39.         cout<<get(l,r)<<"\n";
  40.     }
  41. }
  42.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/emuSTt
language:
C++14 (gcc 8.3)
created:
2 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!