fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4. int A[50001] , Seg[4 * 50001];
  5.  
  6. void built(int l , int r , int p = 1){
  7.     if(l == r) Seg[p] = A[l] ;
  8.     else {
  9.         int mid = (l + r) / 2 ;
  10.         built(l , mid , (p << 1)) ;
  11.         built(mid + 1 , r , 1 + (p << 1)) ;
  12.         Seg[p] = max(Seg[(p << 1)] , Seg[1 + (p << 1)]) ;
  13.     }
  14. }
  15.  
  16. int RMQ(int i , int j , int l , int r , int p = 1){
  17.     // No OVERLAP
  18.     if(l > j || i > r) return INT_MIN ;
  19.  
  20.     // TOTAL OVERLAP
  21.     if(l >= i && j >= r) return Seg[p] ;
  22.  
  23.     int mid = (l + r) / 2 ;
  24.  
  25.     int p1 = RMQ(i , j , l , mid , (p << 1)) ;
  26.     int p2 = RMQ(i , j , mid + 1 , r , 1 + (p << 1)) ;
  27.  
  28.     return max(p1 , p2) ;
  29. }
  30.  
  31. int main(){
  32.     long n ;
  33.     cin >> n ;
  34.     for(int i = 0 ; i < n ; i++)
  35.         cin >> A[i] ;
  36.  
  37.     built(0 , n - 1) ;
  38.  
  39.     int q ;
  40.     cin >> q ;
  41.     while(q--){
  42.         int a , b ;
  43.         cin >> a >> b;
  44.         cout << RMQ(a - 1 , b - 1 , 0 , n - 1) << endl;
  45.     }
  46.  
  47.     return 0 ;
  48. }
  49.  
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/FJiMhD
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!