k=query(x,y-1) if(k==x) count++ with this change ur code ACs :) On Sat, Jun 11, 2011 at 1:24 PM, Radhika Renganathan <radi.coo...@gmail.com>wrote:
> i did the same prob wit range maximum query.. but im repeatedly > getting wrong answer.. im stuck with this prob for a long time.. pls > help.. > > my code: > > #include<iostream> > using namespace std; > #include<stdlib.h> > #include<stdio.h> > int A[50010]; > int M[9999999]; > void initialize(int node, int b, int e) > { > if (b == e) > M[node] = b; > else > { > initialize(2 * node, b, (b + e) / 2); > initialize(2 * node + 1, (b + e) / 2 + 1,e); > if (A[M[2 * node]] >= A[M[2 * node + 1]]) > M[node] = M[2 * node]; > else > M[node] = M[2 * node + 1]; > } > } > int query(int node, int b, int e, int i, int j) > { > int p1, p2; > if (i > e || j < b) > return -9999; > if (b >= i && e <= j) > return M[node]; > p1 = query(2 * node, b, (b + e) / 2,i, j); > p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j); > if (p1 == -9999) > return p2; > if (p2 == -9999) > return p1; > if (A[p1] >= A[p2]) > return p1; > return p2; > > } > > int main() > { > int n,i,t,j,count=0,k,size; > > scanf("%d%d",&n,&t); > > for (i=1;i<=n;i++) > scanf("%d",&A[i]); > > initialize(1,1,n); > for(i=0;i<t;i++) > { > int x,y; > scanf("%d%d",&x,&y); > k=query(1,1,n,x,y); > if(!(x<k && k<y)) > count++; > } > printf("%d",count); > return 0; > } > > > On 6/11/11, KK <kunalkapadi...@gmail.com> wrote: > > Search Topcoder Tutorial Range Minimum Query @ Google... > > By few intuitive changes u can implement Range Maximum Query as well... > > > > -- > > 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. > > > > > > > -- > .... radhika .. :) > > -- > 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.