Monday, March 23, 2020

SpojOJ - GSS1 - Can you answer queris 1

Problem link : https://www.spoj.com/problems/GSS1/

IDEA: To solve this problem first we need to think where we can we get the maximum value in a range.Segment tree makes the problem easier to solve. But storing values in node is the tricky tasks here. Here each node must store more than one value. Maximum value in a range can be in left side or in right side or in both side. So, we will store four informtion in a node. They are total, left sum, right sum, best sum.Best value among these four value will be the answer.

Code:

#include <bits/stdc++.h>

#define min -9999999
#define mx1 (1<<16)
#define mx2 mx1<<2
#define endl '\n'

using namespace std;


struct val
{
    long total,lsum,rsum,best;
};

val *segment = new val[mx2];
int *a = new int[mx1];

int maxof(int f, int g)
{
    if(f>=g)
        return f;
    else
        return g;
}

void simp(int pos)
{
    segment[pos].total = segment[2*pos+1].total+segment[2*pos+2].total;
    segment[pos].lsum = maxof(segment[2*pos+1].lsum,segment[2*pos+1].total+segment[2*pos+2].lsum);
    segment[pos].rsum = maxof(segment[2*pos+2].rsum,segment[2*pos+2].total+segment[2*pos+1].rsum);
    segment[pos].best = maxof(maxof(segment[2*pos+1].best,segment[2*pos+2].best),segment[2*pos+1].rsum+segment[2*pos+2].lsum);
}

void built(int lo,int hi,int  pos)
{
    if(lo==hi)
    {
        segment[pos].total= a[lo];
        segment[pos].lsum= a[lo];
        segment[pos].rsum= a[lo];
        segment[pos].best= a[lo];
        return;
    }
    int mid= lo+(hi-lo)/2;
    built(lo,mid,2*pos+1);
    built(mid+1,hi,2*pos+2);
    simp(pos);
}

val query(int qlo,int qhi,int lo,int hi,int pos)
{
    if(qlo>hi||qhi<lo)
    {
         return (val)
         {
             0,
             min,
             min,
             min
         };
    }
    if(qlo<=lo&&qhi>=hi)
    {
        return segment[pos];
    }
    int mid = lo+(hi-lo)/2;
    val left=query(qlo,qhi,lo,mid,2*pos+1);
    val right = query(qlo,qhi,mid+1,hi,2*pos+2);
    val pr;
    pr.total = left.total+right.total;
    pr.lsum= maxof(left.lsum,left.total+right.lsum);
    pr.rsum= maxof(right.rsum,right.total+left.rsum);
    pr.best= maxof(maxof(left.best,right.best),left.rsum+right.lsum);
    return pr;
}




int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    built(0,n-1,0);
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        x--,y--;
        val res= query(x,y,0,n-1,0);
        int ans=maxof(maxof(res.best,res.total),maxof(res.lsum,res.rsum));
        cout<<ans<<endl;
    }
    return 0;
}

No comments:

Post a Comment