fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 100005
  4. int arr[mx];
  5. int tree[mx*3];
  6.  
  7. void init(int node,int b,int e)
  8. {
  9.     if (b==e) {
  10.         tree[node]=arr[b];
  11.         return;
  12.     }
  13.     int Left=node*2;
  14.     int Right=node*2+1;
  15.     int mid =(b+e)/2;
  16.     init(Left,b,mid);
  17.     init(Right,mid+1,e);
  18.     tree[node]=min(tree[Left],tree[Right]);
  19. }
  20.  
  21. int query(int node, int b, int e, int i, int j)
  22. {
  23.     if (i > e || j < b)
  24.         return mx; //Out of range
  25.     if (b >= i && e <= j)
  26.         return tree[node]; //Relevant Segment
  27.     int Left = node * 2; //need to split
  28.     int Right = node * 2 + 1;
  29.     int mid = (b + e) / 2;
  30.     int p1 = query(Left, b, mid, i, j);
  31.     int p2 = query(Right, mid + 1, e, i, j);
  32.     return min(p1,p2); //sum of left and right side
  33. }
  34.  
  35. int main()
  36. {
  37.     int n,q,x,y,tc,cs=0;
  38.     scanf("%d",&tc);
  39.     while(tc--){
  40.     scanf("%d%d",&n,&q);
  41.     for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
  42.     init(1,1,n);
  43.     printf("Case %d:\n",++cs);
  44.     while(q--){
  45.         scanf("%d%d",&x,&y);
  46.         printf("%d\n",query(1,1,n,x,y));
  47.     }
  48.     }
  49.     return 0;
  50. }
  51.  
  52. /*
  53. 7 3
  54. 4 -9 3 7 1 0 2
  55. */
  56.  
Time limit exceeded #stdin #stdout 5s 8118272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3b9GOx
language:
C++14 (gcc 8.3)
created:
7 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!