fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long a[100001];
  4. long long mn[10000000];
  5. long long mx[10000000];
  6. float maxi(float a,float b,float c)
  7. {
  8.     if(a>b)
  9.     {
  10.         return a>c?a:c;
  11.     }
  12.     else
  13.         return b>c?b:c;
  14. }
  15. void buildtreemn(int node,int l,int r)
  16. {
  17.     if(l==r){
  18.         mn[node]=a[l];
  19.         return; }
  20.     buildtreemn(node*2,l,(l+r)/2);
  21.     buildtreemn(node*2+1,(l+r)/2+1,r);
  22.     if(mn[node*2]<mn[node*2+1])
  23.         mn[node]=mn[node*2];
  24.     else
  25.         mn[node]=mn[node*2+1];
  26. }
  27. void buildtreemx(int node,int l,int r)
  28. {
  29.     if(l==r){
  30.         mx[node]=a[l];
  31.         return; }
  32.     buildtreemx(node*2,l,(l+r)/2);
  33.     buildtreemx(node*2+1,(l+r)/2+1,r);
  34.     if(mx[node*2]>mx[node*2+1])
  35.         mx[node]=mx[node*2];
  36.     else
  37.         mx[node]=mx[node*2+1];
  38. }
  39. int querymn(int node,int l,int r,int i,int j)
  40. {
  41.     int p1,p2;
  42.     if(i>r || j<l)
  43.         return -1;
  44.     if(l>=i && r<=j)
  45.         return mn[node];
  46.     p1=querymn(node*2,l,(l+r)/2,i,j);
  47.     p2=querymn(node*2+1,(l+r)/2+1,r,i,j);
  48.     if (p1 == -1)
  49.           return p2;
  50.       if (p2 == -1)
  51.           return p1;
  52.       if (p1 <= p2)
  53.           return  p1;
  54.       else
  55.           return  p2;
  56. }
  57. int querymx(int node,int l,int r,int i,int j)
  58. {
  59.     int p1,p2;
  60.     if(i>r || j<l)
  61.         return -1;
  62.     if(l>=i && r<=j)
  63.         return mx[node];
  64.     p1=querymx(node*2,l,(l+r)/2,i,j);
  65.     p2=querymx(node*2+1,(l+r)/2+1,r,i,j);
  66.     if (p1 == -1)
  67.           return p2;
  68.       if (p2 == -1)
  69.           return p1;
  70.       if (p1 >= p2)
  71.           return  p1;
  72.       else
  73.           return  p2;
  74. }
  75. int main()
  76. {
  77.     int n,i,j,q;
  78.     cin>>n;
  79.  
  80.     for(i=0;i<n;i++)
  81.         cin>>a[i];
  82.     cin>>q;
  83.     float ans=0;
  84.     buildtreemn(1,0,n-1);
  85.     buildtreemx(1,0,n-1);
  86.     while(q--)
  87.     {
  88.         int l,r;
  89.         cin>>l>>r;
  90.         /*if(n==1)
  91.         {
  92.             cout<<a[0]<<".0\n";
  93.             continue;
  94.         }*/
  95.         int min1=querymn(1,0,n-1,l,r);
  96.         float max1=querymx(1,0,n-1,0,l-1);
  97.         float max2=querymx(1,0,n-1,l,r);
  98.         float max3=querymx(1,0,n-1,r+1,n-1);
  99.         max2=min1+(max2-min1)/2;
  100.         max1+=min1;
  101.         max3+=min1;
  102.         ans=maxi(max1,max2,max3);
  103.         if((ans-floor(ans))!=0)
  104.         cout<<ans<<"\n";
  105.         else
  106.         cout<<ans<<".0\n";
  107.     }
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0s 159744KB
comments (?)
stdin
copy 
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
1
4 10
stdout
copy 
9.0
https://ideone.com/nJYO09
language:
C++ 4.3.2 (gcc-4.3.2)
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!