hii friend..
its my first segment tree problem.but i get WA in 10 test case..all the
test case that i try i got correct answer..can any one find bug in program
and correct me plz
problem http://www.spoj.pl/problems/GSS1/
algo-- i use segment tree
My solution..
#include<iostream>
#include<stdio.h>
using namespace std;
long long int a[50010],tree[300020];
#define MAX(x,y) x>y?x:y
void build(int n,int b,int e)
{
if(b>e)
return;
else if(b==e)
{
tree[n]=a[b];
return;
}
build(n*2,b,(b+e)/2);
build(n*2+1,(b+e)/2+1,e);
long long int temp=MAX(tree[n*2],tree[n*2+1]);
tree[n]=MAX((tree[n*2]+tree[n*2+1]),temp);
return;
}
long long int query(int n,int i,int j,int b,int e)
{
if(i>e||j<b)
return -16000;
else if(i==b&&j==e)
return tree[n];
if(i<=b&&j>=e)
return tree[n];
long long int p1=query(2*n,i,j,b,(b+e)/2);
long long int p2=query(2*n+1,i,j,(b+e)/2+1,e);
long long int temp=MAX(p1,p2);
return (MAX((p1+p2),temp));
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
build(1,0,n-1);
long long int m;
scanf("%lld",&m);
int i,j;
long long int r;
while(m--)
{
scanf("%d%d",&i,&j);
r=query(1,i-1,j-1,0,n-1);
printf("%lld\n",r);
}
return 0;
}
*Anshul Agarwal
*
--
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.
