Jan 2012
1 / 8
Jan 2012
Jun 2022
himma
Jan '12

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;
}

  • created

    Jan '12

  • last reply

    Jun '22
  • 7

    replies

  • 1.0k

    views

  • 6

    users

skulldude
Jan '12

Can you explain why you are checking whether the node is a left,right or interior node? How does it help you find the required answer?

Hint: You have to maintain more information at each node that just the maximum sum.

himma
Jan '12

thanks for your reply...

max sum can be formed from a) left child,
b) right child or
c) adding sum of left and right child
in case (c) , no. must be contiguous.To examine this ,data member 'l' is maintained.
the sum is contiguous when leftchild->l=1 and rightchild->l=0 or (l=2 &&l=0) or( ...) i.e maxsum(leftchild)+maxsum(right child) is valid if maxsum(left child) comes from its rightchild or 'both' and maxsum(rightchild) comes from its leftchild or 'both'.

here both refers to case (c).

i think we can do this problem by adding following data members
1)data
2)maxsum
3)max left sum
4)max right sum

thus at any node maxsum is equals to maximum( maxsum(leftchild),maxsum(rightchild),maxrightsum(4)+max left sum(3))
also updating 3,4 acc.

skulldude
Jan '12

Yes, those are the informations that must be maintained at each node. smile.

22 days later
cegprakash
Feb '12

getting WA frowning frowning

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <utility>
#include <bitset>
#define pb push_back
using namespace std;
int INF=-1e9;
//my first problem in segment tree
int n, arr[50005], sum[10000000], from,to;
inline int max(int a,int b, int c){
     if(a>b&&a>c)
      return a;
     if(b>c)
      return b;
     return c;
}
void initialize(int node, int left, int right){
     if(left==right)
         sum[node]=arr[left];
    else{
          initialize(node*2, left, (left+right)/2);
          initialize(node*2+1, (left+right)/2+1, right);
          sum[node]= max( sum[node*2] , sum[node*2+1], sum[node*2]+sum[node*2+1]); 
    }     
}
int query(int node, int i, int j){
     if(i>=from&&j<=to)
        return sum[node];
     int sum1=INF, sum2=INF;
     if((i+j)/2 >=from)
    sum1=query(node*2,i,(i+j)/2);
 if((i+j)/2+1<=to)
    sum2=query(node*2+1,(i+j)/2+1,j);     
 
 if(sum1==INF)
    return sum2;
 if(sum2==INF)
     return sum1;
 return max(sum1,sum2,sum1+sum2);
}
int main(){
    int t,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
      scanf("%d",&arr[i]);
    scanf("%d",&t);
    initialize(1,0,n-1);
    while(t--){
        scanf("%d %d",&from,&to);
        from--;to--;
        printf("%d\n",query(1,0,n-1) ) ;
    }
    return 0;
}
1 month later
5 years later
shizakhan
Oct '17

I think the output should be 3 in this case. We have 1(at 2nd index) +2 (5th index).

4 years later