fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,q;
  5. vector<int> a;
  6. vector< pair<int,int> > node;
  7. int resmax, resmin;
  8.  
  9. void Init_Tree(int k, int l, int r, int i)
  10. {
  11.     if(l>i || r<i) return;
  12.     if(l==r)
  13.     {
  14.         node[k]=make_pair(a[i],a[i]);
  15.         return;
  16.     }
  17.     int m=(l+r)/2;
  18.     Init_Tree(2*k,l,m,i);
  19.     Init_Tree(2*k+1,m+1,r,i);
  20.     node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
  21. }
  22.  
  23. void Init()
  24. {
  25.     scanf("%d%d",&n,&q);
  26.     a.resize(n+2);
  27.     node.resize(4*n);
  28.     for (int i=1;i<=n;i++)
  29.     {
  30.         scanf("%d",&a[i]);
  31.         Init_Tree(1,1,n,i);
  32.     }
  33. }
  34.  
  35. void Query(int k, int l, int r, int A, int B)
  36. {
  37.     if(l>B || r<A) return;
  38.     if(A<=l && B>=r)
  39.     {
  40.         resmax=max(resmax,node[k].first);
  41.         resmin=min(resmin,node[k].second);
  42.         return;
  43.     }
  44.     int m=(l+r)/2;
  45.     Query(2*k,l,m,A,B);
  46.     Query(2*k+1,m+1,r,A,B);
  47. }
  48.  
  49. void Solve()
  50. {
  51.     for (int i=1;i<=q;i++)
  52.     {
  53.         int A, B;
  54.         scanf("%d%d",&A,&B);
  55.         resmax=0;
  56.         resmin=10000000;
  57.         Query(1,1,n,A,B);
  58.         printf("%dn",resmax-resmin);
  59.     }
  60. }
  61.  
  62. int main()
  63. {
  64.     Init();
  65.     Solve();
  66. }
Success #stdin #stdout 0s 2876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZNMbg0
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years 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!