You are not logged in. Please login at www.codechef.com to post your questions!

×

what's wrong with my code for matchsticks??

can anybody tell me what's wrong with mine code ...i tried to implement range min query algo. but i can't figure out what's wrong it seems correct to me...

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int A[100003],M[300007],C[300007];
 void initializem(int node, int b, int e, int M[], int A[], int N)
  {
      if (b == e)
          M[node] = b;
      else
       {

          initializem(2*node, b, (b + e)/2, M, A, N);
          initializem(2*node + 1, (b + e)/2 + 1,e, M, A, N);

          if (A[M[2 * node]] <= A[M[2 * node + 1]])
              M[node] = M[2 * node];
          else
              M[node] = M[2 * node + 1];
      }
  }

  int minquery(int node, int b, int e, int M[], int A[], int i, int j)
  {
      int p1, p2;




      if (i > e || j < b)
          return -1;


      if (b >= i && e <= j)
          return M[node];


      p1 = minquery(2*node, b, (b + e)/2, M, A, i, j);
      p2 = minquery(2*node + 1, (b + e)/2 + 1, e, M, A, i, j);


      if (p1 == -1)
          return M[node] = p2;
      if (p2 == -1)
          return M[node] = p1;
      if (A[p1] <= A[p2])
          return M[node] = p1;
      return M[node] = p2;


  }

  void initializec(int node, int b, int e, int C[], int A[], int N)
  {
      if (b == e)
          C[node] = b;
      else
       {

          initializec(2*node, b, (b + e)/2, C, A, N);
          initializec(2*node + 1, (b + e)/2 + 1, e, C, A, N);

          if (A[C[2*node]] >= A[C[2*node + 1]])
              C[node] = C[2*node];
          else
              C[node] = C[2*node + 1];
      }
  }

  int maxquery(int node, int b, int e, int C[], int A[], int i, int j)
  {
      int p1, p2;




      if (i > e || j < b)
          return -1;


      if (b >= i && e <= j)
          return C[node];


      p1 = maxquery(2*node, b, (b + e)/2, C, A, i, j);
      p2 = maxquery(2*node + 1, (b + e)/2 + 1, e, C, A, i, j);


      if (p1 == -1)
          return C[node] = p2;
      if (p2 == -1)
          return C[node] = p1;
      if (A[p1] >= A[p2])
          return C[node] = p1;
      return C[node] = p2;


  }


int main()
{
int n,q,l,r,i,j,k,p;
double b,m1,m;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&A[i]);
}
j=4*n;
for(i=0;i<j;i++)
{
 M[i]=-1;
 C[i]=-1;
}
initializem(1,0,n-1,M,A,n);
initializec(1,0,n-1,C,A,n);
scanf("%d",&q);


while(q--)
{
  scanf("%d%d",&l,&r);
   i=minquery(1,0,n-1,M,A,l,r);

   j=maxquery(1,0,n-1,C,A,0,l-1);

   k=maxquery(1,0,n-1,C,A,r+1,n-1);

   m=(A[j]>=A[k])?A[j]:A[k];

   m+=A[i];

   p=maxquery(1,0,n-1,C,A,l,r);
b=double(A[i])+double(A[p]-A[i])/2;
m1=(b>m)?b:m;
    printf("%.1f\n",m1);

}
return 0;
}

asked 15 May '13, 14:21

khitish's gravatar image

3★khitish
45151824
accept rate: 0%

edited 15 May '13, 17:39

betlista's gravatar image

3★betlista ♦♦
16.9k49115225


small question: try l=0,r=n-1;

j=maxquery(1,0,n-1,C,A,0,l-1);

k=maxquery(1,0,n-1,C,A,r+1,n-1);

m=(A[j]>=A[k])?A[j]:A[k];

there might be a issue here as j=-1,k=-1 and so some ambiguous operations

link

answered 15 May '13, 15:13

aashish_iitm's gravatar image

2★aashish_iitm
34647
accept rate: 42%

in addition to what @aashish_iitm said, while returning from the functions don't do return M[node] = p1; just do return p1;

link

answered 15 May '13, 17:38

anuraganand's gravatar image

5★anuraganand
21128
accept rate: 21%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×217
×54
×32

question asked: 15 May '13, 14:21

question was seen: 1,384 times

last updated: 15 May '13, 17:39