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
<[email protected]>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 <[email protected]> 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
