Lazy Propagation - HORRIBLE spoj

Question

I am attempting the problem HORRIBLE from spoj and here's the link: http://www.spoj.com/problems/HORRIBLE/ I am trying to teach myself lazy propagation with segment tree. Following is the code I have written, I have tried to make it as concise and clear as possible, please let me know if something is unclear.

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

typedef long long ll;

ll tree[500010];
ll lazy[500010]={};

void buildST(ll A[], ll STidx, ll l, ll r)
{
    if(l==r)
    {
        tree[STidx]=A[l];
        return;
    }
    ll left=2*STidx, right=left+1, mid=(l+r)/2;
    buildST(A, left, l, mid);
    buildST(A, right, mid+1, r);
    tree[STidx]=tree[left]+tree[right];
}

void update(ll STidx, ll i, ll j, ll l, ll r, ll val)
{
    //printf("%lld %lld %lld %lld %lld\n", STidx, i, j, l, r);
    if(lazy[STidx]!=0)
    {
        tree[STidx]+=(l-r+1)*lazy[STidx];
        if(l!=r)
        {
            lazy[2*STidx]+=lazy[STidx];
            lazy[2*STidx+1]+=lazy[STidx];
        }
        lazy[STidx]=0;
    }
    //printf("1\n");
    if(l>r || l>j || r<i)
        return;
    //printf("1\n");
    if(l>=i && r<=j)
    {
        //printf("%lld\n", STidx);
        tree[STidx]+=(r-l+1)*val;
        if(l!=r)
        {
            lazy[2*STidx]+=val;
            lazy[2*STidx+1]+=val;
        }
        return;
    }
    ll mid=(l+r)/2;
    update(2*STidx, i, j, l, mid, val);
    update(2*STidx+1, i, j, mid+1, r, val);
    tree[STidx]=tree[2*STidx]+tree[2*STidx+1];
}

ll query(ll STidx, ll i, ll j, ll l, ll r)
{
    if(lazy[STidx]!=0)
    {
        tree[STidx]+=lazy[STidx]*(r-l+1);
        if(l!=r)
        {
            lazy[2*STidx]+=lazy[STidx];
            lazy[2*STidx+1]+=lazy[STidx];
        }
        lazy[STidx]=0;
    }
    if(l>r || l>j || r<i)
        return 0;
    if(l>=i && r<=j)
        return tree[STidx];
    ll mid=(l+r)/2;
    ll q1=query(2*STidx, i, j, l, mid);
    ll q2=query(2*STidx+1, i, j, mid+1, r);
    return q1+q2;
}

ll A[100010];

int main()
{
    ll T, N, C, type, p, q, v, i;
    scanf("%lld", &T);
    while(T--)
    {
        scanf(" %lld %lld", &N, &C);
        for(i=0; i<N; ++i)
            A[i]=0;
        for(i=0; i<4*N; ++i)
            lazy[i]=0;
        buildST(A, 1, 0, N-1);
        while(C--)
        {
            scanf(" %lld", &type);
            if(type==0)
            {
                scanf(" %lld %lld %lld", &p, &q, &v);
                update(1, p-1, q-1, 0, N-1, v);
                //for(i=1; i<=15; ++i)
                //  printf("%lld ", tree[i]);
                //printf("\n"); 
            }
            if(type==1)
            {
                scanf(" %lld %lld", &p, &q);
                printf("%lld\n", query(1, p-1, q-1, 0, N-1));
            }
        }
    }
    return 0;
}

The sample testcase provided gives the correct answer with my code but when submitted, I get wrong answer message. I have checked my code a lot of times but I can't find the bug.

Any help is appreciated. Thanks!

Answer 1

One of the error which i can see is that in the update function

instead of tree[STidx]+=(l-r+1)*lazy[STidx]; it should be tree[STidx]+=(r-l+1)*lazy[STidx];