Spoj GSS1 – CPP solution

Link to problem: http://www.spoj.com/problems/GSS1/
The solution is standard: a segment tree where information about the total sum, the maximum left possible, right possible and best sum.

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

struct node {
    long sum;
    long best;
    long left;
    long right;
};

int n;
long q[50003];
node tree[200003];

node makeNode(long sum, long best, long left, long right) {
    node tmp;
    tmp.sum = sum;
    tmp.best = best;
    tmp.left = left;
    tmp.right = right;
    return tmp;
}

node combine (node l, node r) {
    long left = l.left;
    if (l.sum + r.left>left) left =l.sum + r.left;
    long right = r.right;
    if (r.sum + l.right > right) right = r.sum + l.right;
    long best = max(l.right + r.left, max(l.best, r.best));
    return makeNode(l.sum+r.sum,best, left, right);
}

node build(int from, int to, int index) {
    if (from == to) {
        tree[index] = makeNode(q[from], q[from], q[from], q[from]);
        return tree[index];
    }
    int mid = (from+to)/2;
    node l = build(from,mid, (index<<1));
    node r = build(mid+1,to, (index<<1)+1);

    tree[index] = combine(l,r);
    return tree[index];
}

node ans(int index, int from, int to, int a, int b) {
    if (from == a && to == b) {
        return tree[index];
    }
    int mid = (from+to)/2;
    if (b <= mid) {
        return ans((index<<1), from, mid, a, b);
    }
    if (a > mid) {
        return ans((index<<1) + 1, mid+1,to,a,b);
    }
    node l = ans((index<<1), from, mid, a, mid);
    node r = ans((index<<1) + 1, mid+1,to,mid+1,b);
    return combine(l,r);
}


int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&q[i]);
    build(1,n,1);
    int t;
    scanf("%d",&t);
    int a,b;
    for (int i = 0; i < t; ++i) {
        scanf("%d%d",&a,&b);
        printf("%ldn", ans(1,1,n,a,b).best);
    }
    return 0;
}

12 thoughts on “Spoj GSS1 – CPP solution

  1. hey!
    Got the problem in my code … 😛
    in query() function i performed merge operation on segtree itself instead of creating a new node!!
    now it’s working fine.

    thanks for the solution …

  2. Guys can you just simply tell me what this code does bcs what I did Understand is only that it creates some segmented tree and works on it nothing more(
    P.S. Please Help! !

  3. You are asked to calculate the maximum subarray on a given range. We use a segment tree to work on the array and for a segment tree there are the following important operations:
    – query a given range for the right answer (whatever it would be)
    – merge 2 neighboring segments given the critera (it is different for different problems)
    – update operations given what is asked. The udpate can be different.

    In this case, we use the following notion to construct the solution.
    Say, that you are given some array:
    L ……………….. M ……………………… R
    Where L is the beginning, M is the middle and R is the end of the array.
    The biggest subarray can be in 3 places:
    – in L-M meaning the left part
    – in M-R meaning the right part
    – in L-R meaning that it crosses the middle.
    => if we can keep the maximum sum starting at the left, ending at the right and the best one (which could be wherever -> in the middle for example), we can easily combine the results, since if we have all of the info for L-M and M-R, then the answer for L-R is:
    max(max( best of L-M, best M-R), right of L-M + left of M-R)
    You just have to to the updates for all the info when creating the tree. This is what combine() does.

  4. Why i am getting RUN TIME ERROR?
    Here is my code.

    #include
    using namespace std;
    #define M -10000000000000000
    typedef long LL;
    typedef struct
    {
    LL total;
    LL left;
    LL right;
    LL max_i;
    }data_type;
    data_type z,e,c,d;
    //z.max_i=-1000000000000000;
    data_type p[200005];
    LL a[100001];
    data_type build_tree(long int as,long int ae,long int ps)
    {

    if(as==ae)
    {
    p.total=p.left=p.right=p.max_i=a[as];
    return p;
    }
    long int mid=(as+ae)/2;
    c=build_tree(as,mid,2*ps+1);
    d=build_tree(mid+1,ae,2*ps+2);
    p.total=c.total+d.total;
    p.left=max(c.left,c.total+d.left);
    p.right=max(d.right,d.total+c.right);
    p.max_i=max(c.right+d.left,max(c.max_i,d.max_i));
    /*if(ps==0||ps==1||ps==2)
    cout<<p.total<<p.max_i<<p.left<<p.right<<p.centre<<endl;*/
    return p;

    }
    data_type *build(long int n)
    {

    build_tree(0,n-1,0);

    }
    data_type find_max(data_type *p,long int ss,long int se,long int as,long int ae,long int index)
    {

    if(ss==as&&se==ae)
    return (p[index]);
    long int mid=(as+ae)/2;
    if(semid)
    return (find_max(p,ss,se,mid+1,ae,2*index+2));
    c=find_max(p,ss,se,as,mid,2*index+1);
    d=find_max(p,ss,se,mid+1,ae,2*index+2);

    e.total=c.total+d.total;
    e.left=max(c.left,c.total+d.left);
    e.right=max(d.right,d.total+c.right);
    e.max_i=max(c.right+d.left,max(c.max_i,d.max_i));
    return e;

    }
    int main()
    {

    long int n,i,m,c,d;
    cin>>n;
    for(i=0;i<n;i++)
    scanf("%ld",a+i);
    build(n);
    /*for(i=0;i<(2*n-1);i++)
    cout<<(arr[i].max_i)<<"c"<>m;
    for(i=0;i<m;i++)
    {
    scanf("%ld%ld",&c,&d);
    data_type temp=find_max(p,c-1,d-1,0,n-1,0);
    //temp.max_i=max(temp.max_i,temp.total);
    printf("%ldn",(temp.max_i));
    }
    /*for(i=0;i<(2*n-1);i++)
    cout<<arr[i].max_i<<endl;*/

    return 0;

    }

  5. In ans function,how did you cover the case if there is no overlap.
    As I saw in other segment tree examples like min query it returns a max value.

  6. @Vishal
    I didn’t have much time to check your code. I would suggest that you generate some simple test. You are most likely accessing memory which has not been allocated by your program or something of that sorts.

    @depinder
    I am not sure what you are asking. In any case, the invariant is that the maximum could be on the left side, the right side or it can be a merge between the right of the left side and the left of right side.

  7. wrong answer.
    can you help, please?

    #include
    #include
    #include
    #include

    using namespace std;

    const int maxn = 50004;
    long long seg[10*maxn][3];
    pair pos[10*maxn];
    long long a[maxn] , ps[maxn];
    vector< pair< pair , int> > ans;
    int n , m;

    void Build(int id = 1 , int l = 0 , int r = n)
    {
    pos[id].first = l;
    pos[id].second = r;

    if (r – l == 1)
    {
    seg[id][0] = seg[id][1] = seg[id][2] = a[l];
    return;
    }

    int mid = (l + r)/2;
    Build(2*id , l , mid );
    Build(2*id + 1 , mid , r);

    seg[id][0] = max(seg[2*id][0] , ps[mid-1] – ps[l – 1] + max( (long long)0 ,seg[2*id + 1][0]) );
    seg[id][2] = max(seg[2*id + 1][2] , ps[r-1] – ps[mid-1] + max( (long long)0 , seg[2*id][2]) );

    seg[id][1] = max( max(seg[2*id][1] , seg[2*id + 1][1]) , max(seg[id][0] , seg[id][2]) );
    seg[id][1] = max(seg[id][1] , max(seg[2*id][2] , max(seg[2*id + 1][0], seg[2*id][2] + seg[2*id + 1][0] ))) ;

    }

    void Solve(int x , int y , int l = 0 , int r = n , int id = 1)
    {
    if (x >= r || y <= l)
    {
    return;
    }
    if (x <= l && r<=y)
    {
    ans.push_back( make_pair(pos[id] , id) );
    return;
    }
    int mid = (l + r)/2 ;
    Solve(x , y , l , mid , 2*id);
    Solve(x , y , mid , r , 2*id + 1);
    }

    int main()
    {
    ios::sync_with_stdio(false);

    scanf("%d" , &n);
    for (int i = 0 ; i < n ; i++)
    {
    scanf("%I64d" , &a[i]);
    }
    ps[-1] = 0;
    ps[0] = a[0];
    for (int i = 1 ; i < n ;i++)
    {
    ps[i] = ps[i-1] + a[i];
    }
    Build();
    scanf("%d" , &m);
    for (int i = 0 ; i < m ;i++)
    {
    ans.clear();
    int x , y;
    scanf("%d %d" , &x , &y);
    x–;
    Solve(x , y);
    sort(ans.begin() , ans.end() );

    long long out = -999999999;
    for (int i = 0 ; i < ans.size() ; i++)
    {
    //printf("%d %dn" , ans[i].first.first , ans[i].first.second);
    out = max(out , seg[ans[i].second][1]);
    out = max(out , seg[ans[i].second][0]);
    out = max(out , seg[ans[i].second][2]);
    }

    for (int i = 0 ; i < ans.size() ; i++)
    {
    for (int j = i + 1; j 1)
    {
    t = 0;
    }
    out = max(out , max( t , seg[ans[i].second][2]) + ps[ans[j].first.first – 1]-ps[ ans[i].first.second – 1] + max( t,seg[ans[j].second][0]));
    }
    }

    out = max(out , seg[ans[0].second ][0]);
    out = max(out , seg[ans.back().second][2]);

    for (int i = 1; i = 0 ; i–)
    {
    out = max(out, ps[ans.back().first.second -1] – ps[ans[i].first.second – 1] + seg[ans[i].second][2]);
    }
    printf(“%I64dn” , out);
    }

    return 0;
    }

  8. #include
    #include
    using namespace std;
    struct node
    {
    long long int prefixsum,suffixsum, sum, maxsum;
    };
    //typedef node an;
    node seg[200009];
    long long int a[50005];
    int n;
    void build(int node,int i,int j)
    {
    if(i==j)
    {
    seg[node].prefixsum=a[i];
    seg[node].suffixsum=a[i];
    seg[node].sum=a[i];
    seg[node].maxsum=a[i];
    return;

    }
    int mid=(i+j)/2;
    int lc=node<<1;
    int rc=lc+1;
    build(node<<1,i,mid);

    build((node<en||jj)
    {
    temp.maxsum=-9999999999999;
    temp.prefixsum=-999999999999;
    temp.suffixsum=-999999999999;
    temp.sum=-9999999999999;
    return temp;
    }*/
    if(i==st&&j==en)
    {
    return seg[node];
    }
    int mid=(st+en)/2;
    int lc=node<=j)
    return query(lc,i,j,st,mid);
    if(mid<i)
    return query(rc,i,j,mid+1,en);
    l1=query(lc,i,mid,st,mid);
    r1=query(rc,mid+1,j,mid+1,en);
    ans.prefixsum=max(l1.prefixsum,l1.sum+r1.prefixsum);
    ans.suffixsum=max(l1.suffixsum+r1.sum,r1.suffixsum);
    ans.sum=l1.sum+r1.sum;
    ans.maxsum=max(l1.maxsum,max(r1.maxsum,l1.suffixsum+r1.prefixsum));
    return ans;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
    scanf("%lld",&a[i]);
    }
    build(1,1,n);
    int m;
    scanf("%d",&m);
    while(m–)
    {
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%lldn",query(1,l,r,1,n).maxsum);
    }
    return 0;
    }
    why this code gives wa

  9. Любопытно, что на job interviews теперь проводят параллели не только inilne/macro, но и macro/templates. По крайней мере, у Microsoft так.

  10. Pingback: Segment Trees GSS1 GSS3 | The Prodigal Prodigy.

Leave a Reply

Your email address will not be published. Required fields are marked *