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.
