i m getting a wa after 9 test case
Can someone provide me a test case where i m wrong.
my approach: each node has two members->
1)data 2)l :which is 0 if that interior node is made from a left child.
1, right child
2,if it is leaf node or that interior node is made from merging.
thus at each interior node,i check left child,right child and one form after merging.
#include <stdlib.h>
#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 300010
#define MIN -10001
typedef struct node{
int data,l;}node;
node M[MAX];
int a[50000];
node maxi(node a,node b)
{
node n;
if(a.data>b.data)
{ n.data=a.data,n.l=0;}
else if(b.data>a.data)
{n.data=b.data,n.l=1;}
else
{
n.data=b.data;
n.l=2;
}
return n;
}
void initialize(int nod, int b, int e, int dir)
{
if (b == e)
{ M[nod].data = a[b];
M[nod].l = 2;
//cout<<"node "<<nod<<"a data"<<M[nod].data<<"a dir"<<M[nod].l<<endl;
}
else
{
initialize(2 * nod, b, (b + e) / 2,0);
initialize(2 * nod + 1, (b + e) / 2 + 1, e,1);
node p1,p2,n;
p1=M[2 * nod],p2= M[2 * nod + 1];
int t=p1.data+p2.data;node
d=maxi(p1,p2);
if((p1.l==1&&p2.l==0)||(p1.l==2&&p2.l==0)||(p1.l==1&&p2.l==2)||(p1.l==2&&p2.l==2))
{
if(d.data>t)
{
M[nod]=d;
}
else
{
n.data=t;n.l=2;
M[nod]=n;
}
}
else{
M[nod]=d;
}
//cout<<"node "<<nod<<"a "<<M[nod].data<<"a dir"<<M[nod].l<<endl;
}
}
node query(int nod, int b, int e, int i, int j)
{
node p1, p2;
node n;
if (i > e || j < b)
{
n.data=MIN;return n;
}
if (b >= i && e <= j)
{
n.data=M[nod].data;
n.l=M[nod].l;
return n;
}
p1 = query(2 * nod, b,(b + e) / 2 ,i, j);
p2 = query(2 * nod + 1, (b + e) / 2 + 1, e, i, j);
if (p1.data == MIN)
return p2;
if (p2.data == MIN)
return p1;
int t=p1.data+p2.data;node d=maxi(p1,p2);
if((p1.l==1&&p2.l==0)||(p1.l==2&&p2.l==0)||(p1.l==1&&p2.l==2)||(p1.l==2&&p2.l==2)) {
if(d.data>t)
{
return d;
}
else
{
n.data=t;n.l=2;
return n;
}
}
else{
return d;
}
}
int main()
{
int n,m,x,y;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<MAX;i++)
M[i].data=-1;
initialize(1,0,n-1,0);
cin>>m;
node no;
for(int i=0;i<m;i++)
{
cin>>x>>y;
no=query(1,0,n-1,x-1,y-1);
cout<<no.data<<endl;;
}
return 0;
}