fork download 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int power[21],A[100001],M[100001][21],M1[100001][21];
  6.  
  7. int MinTime(int i, int j)
  8. {
  9.         int k = log2(j-i+1);
  10.         return (A[M[i][k]] <= A[M[j-power[k]+1][k]]) ? A[M[i][k]] : A[M[j-power[k]+1][k]];
  11. }
  12.  
  13. int MaxTime(int i, int j)
  14. {
  15.         int k = log2(j-i+1);
  16.         return (A[M1[i][k]] >= A[M1[j-power[k]+1][k]]) ? A[M1[i][k]] : A[M1[j-power[k]+1][k]];
  17. }
  18.  
  19. void RMQ_MIN(int n)
  20. {
  21.     int i, j;
  22.     for (i = 0; i < n; i++) M[i][0] = i;
  23.  
  24.     for (j = 1; power[j] <= n; j++)
  25.         {
  26.                 for (i = 0; i + power[j] - 1 < n; i++)
  27.                 {
  28.                         M[i][j] = (A[M[i][j - 1]] < A[M[i + power[j-1]][j - 1]]) ? M[i][j - 1] : M[i + power[j-1]][j - 1];
  29.                 }
  30.         }
  31. }
  32.  
  33. void RMQ_MAX(int n)
  34. {
  35.         int i,j;
  36.         for(i = 0; i < n; i++) M1[i][0] = i;
  37.  
  38.         for(j = 1; power[j] <= n; j++)
  39.         {
  40.                 for (i = 0; i + power[j] - 1 < n; i++)
  41.                 {
  42.                     M1[i][j] = (A[M1[i][j - 1]] > A[M1[i + power[j-1]][j - 1]]) ? M1[i][j - 1] : M1[i + power[j-1]][j - 1];
  43.                 }
  44.         }
  45. }
  46.  
  47. int main()
  48. {
  49.     double Ans,FastTime;
  50.     int i,N,Q,L,R,Min1,Max1,Max2,Max3,Max4;
  51.  
  52.     power[0] = 1;
  53.     for(i=1; i<=20; i++) power[i] = 2*power[i-1];
  54.  
  55.     scanf("%d",&N);
  56.     for(i=0; i<N; i++) scanf("%d",&A[i]);
  57.  
  58.     RMQ_MIN(N);
  59.     RMQ_MAX(N);
  60.  
  61.     scanf("%d",&Q);
  62.     while(Q--)
  63.     {
  64.         scanf("%d%d",&L,&R);
  65.         Min1 = MinTime(L,R);
  66.         //printf("%d ",Min1);
  67.         Max1 = MaxTime(L,R);
  68.         //printf("%d ",Max1);
  69.         FastTime = (Max1-Min1)/2.0;
  70.         //printf("%d ",FastTime);
  71.         Max2 = (L > 0) ? MaxTime (0,L-1) : 0;
  72.         Max3 = (R < N-1) ? MaxTime(R+1, N-1) : 0;
  73.         Max4 = max(Max2 + 0.0, Max3 + 0.0);
  74.         Ans  = Min1 + max( FastTime ,  Max4 + 0.0 );
  75.         printf("%.1lf\n",Ans);
  76.     }
  77.   return 0;
  78. }
Success #stdin #stdout 0s 19696KB
comments (?)
stdin 
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
3
4 10
0 0
17 17
stdout 
9.0
15.0
14.0
https://ideone.com/lLzB7a
language:
C++14 (gcc 8.3)
created:
11 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!