fork download
copy 
  1.  #include<iostream>
  2.  using namespace std;
  3.  #define inf 0x7fffffff
  4.  int arr[500000];   //WHY WE DEFINE IT GLOBALLLY
  5.  int segtree[500000];   //WHY WE DEFINE IT GLOBALLY
  6.  void constructtree(int low,int high,int pos);
  7.  int rangemaxquery(int qlow,int qhigh,int low,int high,int pos);
  8.  
  9.  int main()
  10.  {
  11.  int m,xi,yi,y;
  12.  long long int n,i;
  13.  cin>>n;
  14.  for(i=0;i<n;i++)
  15.   {
  16.    cin>>arr[i];
  17.   }
  18.  cin>>m;
  19.  constructtree(0,i,0);
  20.  while(m--)
  21.   {
  22.   cin>>xi>>yi;
  23.   y=rangemaxquery(xi,yi,0,i,0);
  24.   cout<<y<<"\n";
  25.   }
  26.  return 0;
  27.  }
  28.  
  29.   void constructtree(int low,int high,int pos)
  30.   {
  31.   if (low==high)
  32.    {
  33.    segtree[pos]=arr[low];
  34.    return ;
  35.  
  36.    }
  37.    int mid=(low+high)/2;
  38.  
  39.     constructtree(low,mid,2*pos+1);
  40.     constructtree(mid+1,high,2*pos+2);
  41.     segtree[pos]=max(segtree[2*pos+1],segtree[2*pos+2]);
  42.  
  43.     }
  44.  
  45.    int rangemaxquery(int qlow,int qhigh,int low,int high,int pos)
  46.     {
  47.      if(qlow<=low&&qhigh>=high)
  48.       return segtree[pos];
  49.  
  50.      if(qlow>high||qhigh<low)
  51.      return -inf;//don't know
  52.  
  53.     int mid=(low+high)/2;
  54.     return       max(rangemaxquery(qlow,qhigh,low,mid,2*pos+1),rangemaxquery(qlow,qhigh,mid+1,high,2*pos+2));}
Time limit exceeded #stdin #stdout 5s 7360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zzNVEO
language:
C++14 (gcc 8.3)
created:
8 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!