fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring> //For memset
  4. #include<climits>
  5. #include<cmath>
  6.  
  7. #define MAX 402 
  8. #define inf LONG_MAX
  9. using namespace std ;
  10.  
  11. long long arr[MAX];
  12.  
  13. //function definition
  14. //void update(long long node, long long a, long long b, long long i, long long j , long long value);
  15. long long query(long long node , long long a , long long b , long long i , long long j, long long []);
  16.  
  17. void build_tree(long long node, long long a, long long b, long long []);
  18.  
  19. //function to find the middle value
  20. inline long long getMid (long long a , long long b){
  21.     return (a+b)/2;
  22. }
  23.  
  24. //Find the maximum of three numbers
  25. inline long long max(long long a , long long b , long long c){
  26.     if (a > b){
  27.         if(a > c)
  28.             return a ;
  29.         else 
  30.             return c ;
  31.     }
  32.     else{
  33.         if(b > c)
  34.             return b ;
  35.         else 
  36.             return c ;
  37.     }
  38. }
  39.  
  40. //Build segment tree
  41. void build_tree(long long node , long long a , long long b, long long tree[]){
  42.     if (a > b){
  43.         return ; // out of range
  44.     }
  45.     if(a == b){
  46.         tree[node] = arr[a];
  47.         return ;
  48.     }
  49.     long long mid = getMid(a , b);
  50.     build_tree(node*2 , a , mid, tree);
  51.     build_tree(node*2+1 , mid+1 , b, tree);
  52.     tree[node] = (tree[node*2] + tree[node*2 + 1]);
  53. }
  54.  
  55. long long queryUtil(long long node , long long i , long long j, long long tree [] ){
  56.     if(i == j){ //Leaf node
  57.         return tree[node];
  58.     }
  59.     else{ //Other nodes
  60.         long long mid = getMid( i , j);
  61.         long long result = max(queryUtil(node*2 , i , mid, tree) , queryUtil(node*2 + 1 ,mid+1 ,j, tree) , tree[node]);
  62.         return result ; 
  63.     }
  64. }
  65.  
  66. //Query tree
  67. long long query(long long node , long long a , long long b , long long i , long long j, long long tree []){
  68.     if(a > b || a > j || b < i)
  69.         return -inf; // Out of range
  70.  
  71.     if(a >= i && b <= j) // Current segment is totally within range [i, j]
  72.         return queryUtil(node , i , j, tree); 
  73.  
  74.     long long mid = getMid(a , b);
  75.     long long q1 = query(node*2, a, mid, i, j, tree); // Query left child
  76.     long long q2 = query(1+node*2, mid + 1, b, i, j, tree); // Query right child
  77.  
  78.     long long res = max(q1 , q2);// Return final result
  79.  
  80.     return res;
  81. }
  82.  
  83. //Driver Program
  84. int main()
  85. {
  86.     long long n ,i , l , r , m ; 
  87.     long long *tree;
  88.     long long h  ;
  89.     //cout << "Enter the number of elements in the array\t";
  90.     cin >> n ;
  91.  
  92.     //Input
  93.     for(i = 1 ;i<=n;i++){
  94.         cin >> arr[i];
  95.     }
  96.     h = ceil(log2(n));
  97.     tree = new long long [ (long long) ( pow (2,  h+ 1) ) ];
  98.     //initializing the array
  99.     memset(tree , 0, sizeof(tree));
  100.     //Build Tree
  101.     build_tree(1 , 1, n, tree);
  102.     cin >> m ;
  103.     while(m--){
  104.         cin >> l >> r ;
  105.         cout << query(1 , 1 , n , l , r, tree) << endl;
  106.     }
  107. return 0 ;
  108. }
Time limit exceeded #stdin #stdout 5s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MfYp0j
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!