fork(1) download
copy 
  1. //
  2. //  mstick.cpp
  3. //  
  4. //
  5. //  Created by Gaurav Gulzar on 22/01/14.
  6. //
  7. //
  8.  
  9. #include <iostream>
  10. using namespace std;
  11. #include <cmath>
  12. #include <cstdio>
  13. double *a;
  14. int *mn,*mx, n;
  15. //int a[] = {2,4,3,1,6,7,8,9,1,7};
  16. //int mn[32],mx[32];
  17. void initialize(int node, int b, int e){
  18.     if(b==e) {
  19.         mx[node] = b;
  20.         mn[node] = b;
  21.         return;
  22.     }
  23.     initialize(2*node, b, (b+e)/2);
  24.     initialize(2*node+1,(b+e)/2 + 1, e);
  25.     mn[node] = ((a[mn[2*node]] <= a[mn[2*node+1]]) ? mn[2*node] : mn[2*node+1]);
  26.     mx[node] = (a[mx[2*node]] >= a[mx[2*node+1]]) ? mx[2*node] : mx[2*node+1];
  27. }
  28.  
  29. int query_min(int node, int b, int e, int i, int j){
  30.     if(i>e || j<b)
  31.         return -1;
  32.  
  33.     if(i<=b && j>=e)
  34.         return mn[node];
  35.  
  36.     int p1 = query_min(2*node,b,(b+e)/2,i,j);
  37.     int p2 = query_min(2*node+1,(b+e)/2+1,e,i,j);
  38.  
  39.     if(p1==-1)
  40.         return mn[node] = p2;
  41.     if(p2==-1)
  42.         return mn[node] = p1;
  43.     if(a[p1]<=a[p2])
  44.         return mn[node] = p1;
  45.     return mn[node] = p2;
  46. }
  47.  
  48. int query_max(int node, int b, int e, int i, int j){
  49.     if(i>e || j<b)
  50.         return -1;
  51.  
  52.     if(i<=b && j>=e)
  53.         return mx[node];
  54.     int p1 = query_max(2*node,b,(b+e)/2,i,j);
  55.     int p2 = query_max(2*node+1,(b+e)/2+1,e,i,j);
  56.  
  57.     if(p1 == -1)
  58.         return mx[node] = p2;
  59.     if(p2 == -1)
  60.         return mx[node] = p1;
  61.     if(a[p1]>=a[p2])
  62.         return mx[node] = p1;
  63.     return mx[node] = p2;
  64. }
  65.  
  66. int main() {
  67.     /*int a[] = {2,4,3,1,6,7,8,9,1,7};
  68.     //int n = sizeof(a)/sizeof(a[0]);
  69.     //int m[32];
  70.     for(int i=0; i<32; i++)
  71.         mn[i] = -1;
  72.     for(int i=0; i<32; i++)
  73.         mx[i] = -1;
  74.     
  75.     initialize(1,0,9);
  76.     for(int i=0; i<32; i++)
  77.         cout << mn[i] << " ";
  78.     cout << "\n";
  79.     cout << query_min(1,0,9,2,6) << " "<< query_max(1,0,9,2,6)<<"\n";*/
  80.     cin >> n;
  81.     double t[n];
  82.     for(int i=0; i<n; i++)
  83.         scanf("%lf",&t[i]);
  84.  
  85.     int q;
  86.     cin >> q;
  87.     int l,r;
  88.     a = t;
  89.     //for(int i=0; i<n; i++)
  90.       //  printf("%.1f ",a[i]);
  91.  
  92.     int s = (int)(log10(n)/log10(2));
  93.     s = 2*( int)(pow(2.0f,(s+1)));
  94.     int t2[s],t3[s];
  95.     for(int i=0;i<s;i++)
  96.         t2[i] = t3[i] = -1;
  97.     mn = t2;
  98.     mx = t3;
  99.     initialize(1,0,n-1);
  100.     for(int i=0; i<q; i++){
  101.         scanf("%d %d",&l,&r);
  102.         int v1 = query_min(1,0,n-1,l,r) ;
  103.         int v2 = query_max(1,0,n-1,l,r);
  104.         //cout << v1 <<v2<< "\n";
  105.  
  106.         int vr1 = query_max(1,0,n-1,0,l-1);
  107.         int vr2 = query_max(1,0,n-1,r+1,n-1);
  108.         double m = (a[vr1] >= a[vr2]?a[vr1]:a[vr2]);
  109.         m = ((m+a[v1] >= a[v1]+(a[v2]-a[v1])/2.0)? m+a[v1] : a[v1]+(a[v2]-a[v1])/2.0);
  110.         printf("%.1lf\n",m);
  111.     }
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
6
3 4 5 1 2 3
1
0 0
stdout
copy 
8.0
https://ideone.com/sbcpML
language:
C++ (gcc 8.3)
created:
10 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!