anyone ?? --
Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Tue, Aug 2, 2011 at 1:57 PM, Amol Sharma <amolsharm...@gmail.com> wrote: > hi, > > i attempted the problem http://www.spoj.pl/problems/GSS1/ > > i have the solved the problem using segment trees.....i have the checked my > solution for the most of the cases it is working fine.....but i am getting > WA.......plz tell any case where my code fails !!.....please point out the > bug if any in the code > > #include<stdio.h> > // SEGEMENT TREE > // this program will make a segment tree of a given array and then perform > the queries on it as asked in the question fo any range > > //starting with the function to ionitialise the segement tree > > > // INTIALIZATION > void initialize(int node, int b, int e, int M[], int A[]) > { > if (b == e) > M[node] = A[b]; > else > { > //compute the values in the left and right subtrees > initialize(2 * node, b, (b + e) / 2, M, A); > initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A); > //search for the minimum value in the first and > //second half of the interval > if (M[2 * node] >= M[2 * node + 1]) > M[node] = M[2 * node]; > else > M[node] = M[2 * node + 1]; > } > } > > > //function for doing query on the segement tree > // QUERY > > int query(int node, int b, int e, int M[], int A[], int i, int j) > { > int p1, p2; > > //if the current interval doesn't intersect > //the query interval return -1 > if (i > e || j < b) > return -1; > > //if the current interval is included in > //the query interval return M[node] > if (b >= i && e <= j) > return M[node]; > > //compute the minimum position in the > //left and right part of the interval > p1 = query(2 * node, b, (b + e) / 2, M, A, i, j); > p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j); > > //return the position where the overall > //minimum is > if (p1 == -1) > return /*M[node] =*/ p2; > if (p2 == -1) > return /*M[node] =*/ p1; > if (p1 >= p2) > return /*M[node] =*/ p1; > return /*M[node] =*/ p2; > } > > int A[50000]={0},M[100000]={-1}; > > int main() > { > int n,i,j,tc; > scanf("%d",&n);//now number of elements in the array is known > for(i=0;i<n;i++) > scanf("%d",&A[i]); > > //initialize your segement tree now > > initialize(1,0,n-1,M,A); > > /* for(i=0;i<2*n;i++) > printf("%d ",M[i]); > printf("\n"); > */ > //perform the queries here > scanf("%d",&tc); > while(tc--) > { > scanf("%d%d",&i,&j); > //perform the query for each interval > printf("%d\n",query(1,0,n-1,M,A,i-1,j-1)); > > //print the maximun value here > } > > return 0; > } > > > > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
