ohhh...i misread the read....blunder...anyways thnx for pointing it out --
Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Tue, Aug 2, 2011 at 7:14 PM, amit karmakar <amit.codenam...@gmail.com>wrote: > 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. > > -- 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.
