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.
