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