fork download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. #define MAX 1000000
  4. #define MAX_MIN 10000 // > sqrt(MAX) 
  5. #define INF 10000000
  6. #define min(a,b) a<b?a:b
  7. #define max(a,b) a>b?a:b
  8.  
  9. int minarr[MAX_MIN];
  10. int maxarr[MAX_MIN];
  11.  
  12. int findmin(int arr[],int st,int en){
  13. int i;
  14. int small=arr[st];
  15. for(i=st+1;i<en;i++){
  16.   if(small>arr[i])
  17.     small=arr[i];
  18. }
  19. return small;
  20. }
  21.  
  22. int calmin(int a[],int n,int root){
  23. int m=0,i;
  24. for(i=0;i<n;i+=root) {
  25.    if(n>i+root)
  26.     minarr[m++]=findmin(a,i,i+root);
  27.    else
  28.     minarr[m++]=findmin(a,i,n);
  29. }
  30. return m;
  31. }
  32.  
  33. int calmax(int a[],int n,int root){
  34.  int m=0,i;
  35.  for(i=0;i<n;i+=root) {
  36.    if(n>i+root)
  37.     maxarr[m++]=findmin(a,i,i+root);
  38.    else
  39.     maxarr[m++]=findmin(a,i,n);
  40. }
  41.  return m;
  42. }
  43.  
  44. int querymin(int L, int R,int root,int a[])
  45. {
  46.   int i;
  47.   if(L > R)
  48.    return INF;
  49.   int lblock = L/root, rblock = R/root;
  50.   int val = INF;
  51.   if(lblock == rblock)
  52.    for(i = L; i <= R; i++)
  53.     val = min(val, a[i]);
  54.   else
  55.   {
  56.    for(i = L; i < (lblock+1)*root; i++)
  57.     val = min(val, a[i]);
  58.    for(i = lblock+1; i < rblock; i++)
  59.     val = min(val, minarr[i]);
  60.    for(i = rblock*root; i <= R; i++)
  61.     val = min(val, a[i]);
  62.   }
  63.  return val;
  64. }
  65.  
  66. int querymax(int L, int R,int root,int a[])
  67. {
  68.   int i;
  69.   if(L > R)
  70.    return INF;
  71.   int lblock = L/root, rblock = R/root;
  72.   int val = INF;
  73.   if(lblock == rblock)
  74.    for(i = L; i <= R; i++)
  75.     val = min(val, a[i]);
  76.   else
  77.   {
  78.    for(i = L; i < (lblock+1)*root; i++)
  79.     val = min(val, a[i]);
  80.    for(i = lblock+1; i < rblock; i++)
  81.     val = min(val, maxarr[i]);
  82.    for(i = rblock*root; i <= R; i++)
  83.     val = min(val, a[i]);
  84.   }
  85.  return val;
  86. }
  87.  
  88. int main(){
  89.  int i,m,n,root,q;
  90.  int beg,end;
  91. int maxq[MAX],minq[MAX];
  92.  int t,t1,t2,t3,t4;
  93.  double ans;
  94.  scanf("%d",&n);
  95.  root=(int)sqrt(n);
  96.  for(i=0;i<n;i++) {
  97.     scanf("%d",&minq[i]);
  98.     maxq[i]=(-1*minq[i]);
  99.  }
  100.  calmin(minq,n,root);
  101.  calmax(maxq,n,root);
  102.  scanf("%d",&q);
  103.  for(i=0;i<q;i++) {
  104.   scanf("%d %d",&beg,&end);
  105.         t=querymin(beg,end,root,minq);
  106.         t1=-1*querymax(beg,end,root,maxq);
  107.         t2=-1*querymax(0,beg-1,root,maxq);
  108.         t3=-1*querymax(end+1,n-1,root,maxq);
  109.         t4=max(t2,t3);
  110.         ans = max( (t1-t)/2.0,t4*1.0);
  111.             ans=ans+t/1.0;
  112.             printf("%.1lf\n", ans + 0.01);
  113.      }
  114.      return 0;
  115.    }
Success #stdin #stdout 0s 9608KB
comments (?)
stdin
copy 
36
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2 3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
3
1 10
20 36
3 36
stdout
copy 
13.0
12.0
6.0
https://ideone.com/PLZU4d
language:
C (gcc 8.3)
created:
10 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!