WA in MSTICK

general
1

I am trying to solve in O(Qroot(N)) but getting WA.
I am not getting where I am failing, Please check my solution.

#include<stdio.h>
#include<math.h>
#define MAX 1000000
#define MAX_MIN 10000 // > sqrt(MAX) 
#define INF 10000000
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b

int minarr[MAX_MIN];
int maxarr[MAX_MIN];

int findmin(int arr[],int st,int en){
int i;
int small=arr[st];
for(i=st+1;i<en;i++){
  if(small>arr[i])
    small=arr[i];
}
return small;
}

int calmin(int a[],int n,int root){
int m=0,i;
for(i=0;i<n;i+=root) {
   if(n>i+root)
    minarr[m++]=findmin(a,i,i+root);
   else
    minarr[m++]=findmin(a,i,n);
}
return m;
}

int calmax(int a[],int n,int root){
 int m=0,i;
 for(i=0;i<n;i+=root) {
   if(n>i+root)
    maxarr[m++]=findmin(a,i,i+root);
   else
    maxarr[m++]=findmin(a,i,n);
}
 return m;
}

int querymin(int L, int R,int root,int a[])
{
  int i;
  if(L > R)
   return INF;
  int lblock = L/root, rblock = R/root;
  int val = INF;
  if(lblock == rblock)
   for(i = L; i <= R; i++)
    val = min(val, a[i]);
  else
  {
   for(i = L; i < (lblock+1)*root; i++)
    val = min(val, a[i]);
   for(i = lblock+1; i < rblock; i++)
    val = min(val, minarr[i]);
   for(i = rblock*root; i <= R; i++)
    val = min(val, a[i]);
  }
 return val;
}

int querymax(int L, int R,int root,int a[])
{
  int i;
  if(L > R)
   return INF;
  int lblock = L/root, rblock = R/root;
  int val = INF;
  if(lblock == rblock)
   for(i = L; i <= R; i++)
    val = min(val, a[i]);
  else
  {
   for(i = L; i < (lblock+1)*root; i++)
    val = min(val, a[i]);
   for(i = lblock+1; i < rblock; i++)
    val = min(val, maxarr[i]);
   for(i = rblock*root; i <= R; i++)
    val = min(val, a[i]);
  }
 return val;
}

int main(){
 int i,m,n,root,q;
 int beg,end;
int maxq[MAX],minq[MAX];
 int t,t1,t2,t3,t4;
 double ans;
 scanf("%d",&n);
 root=(int)sqrt(n);
 for(i=0;i<n;i++) {
    scanf("%d",&minq[i]);
    maxq[i]=(-1*minq[i]);
 }
 calmin(minq,n,root);
 calmax(maxq,n,root);
 scanf("%d",&q);
 for(i=0;i<q;i++) {
  scanf("%d %d",&beg,&end);
        t=querymin(beg,end,root,minq);
        t1=-1*querymax(beg,end,root,maxq);
        t2=-1*querymax(0,beg-1,root,maxq);
        t3=-1*querymax(end+1,n-1,root,maxq);
        t4=max(t2,t3);
        ans = max( (t1-t)/2.0,t4*1.0);
            ans=ans+t/1.0;
            printf("%.1lf\n", ans + 0.01);
     }
     return 0;
   }
2

Kindly post your question on the respective editorials. It will get answered better there. Here’s the link to the editorial: http://discuss.codechef.com/questions/9722/mstick-editorial

3

okay and thank you… if possible then delete this post.