Do you understand the problem properly ? >From your code it seems you don't understand the problem. Can you explain the approach that you have implemented?
On Aug 2, 5:13 pm, Amol Sharma <amolsharm...@gmail.com> wrote: > 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.
