Sarthak_8's blog

By Sarthak_8, history, 7 years ago, In English

Hello all. I am solving the problem here SPOJ Horrible Queries but getting WA. I am solving it using segment tree with lazy propogation. I am not able to figure out the error in my code. It seems, it fails on the edge cases as it is giving negative values on some edge cases. I can't understand the error in my code? Here's the code.

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int counter = 0;

void update(long long tree[], long long lazy[], int node, int range_start, int range_end, int l, int r, int val)
{
    if(lazy[node] != 0)     //First we check if corresponding node in lazy array is up-to-date or not.
    {
        tree[node] += (range_end - range_start + 1) * lazy[node];       //Update corresponding tree node if lazy[node] not up-to-date.
        if(range_start != range_end)        //Also if this is not the leaf node propagate the lazy[node] value to children of current node i.e. lazy[node].
        {
            lazy[2*node] += lazy[node];     //Propagating value to left child
            lazy[2*node + 1] += lazy[node];     //Propagating value to right child
        }
        lazy[node] = 0;     //Reset the node as it is now updated and values propagated to its children.
    }
    if(range_start > range_end or range_start > r or range_end < l)     //No Overlap so just stop and return.
        return ;
    if(range_start >= l and range_end <= r)        //Total Overlap.
    {
        tree[node] += (range_end - range_start + 1)*val;
        if(range_start != range_end)
        {
            lazy[2*node] += val;
            lazy[2*node + 1] += val;
        }
        return;
    }
    int mid = (range_start + range_end)/2;
    update(tree, lazy, 2*node, range_start, mid, l, r, val);
    update(tree, lazy, 2*node + 1, mid + 1, range_end, l, r, val);
    tree[node] = tree[2*node] + tree[2*node + 1];
}

long long query(long long tree[], long long lazy[], int node, int range_start, int range_end, int l, int r)
{
    if(range_start > range_end or range_start > r or range_end < l)     //No Overlap.
        return 0;

    if(lazy[node] != 0)
    {
        if(range_start == range_end)
            tree[node] += lazy[node];
        else
        {
            tree[node] += (range_end - range_start + 1)*lazy[node];
            lazy[2*node] = lazy[node];
            lazy[2*node + 1] = lazy[node];
        }
        lazy[node] = 0;
    }

    if(range_start >= l and range_end <= r)
        return tree[node];
    int mid = (range_start + range_end)/2;
    int p1 = query(tree, lazy, 2*node, range_start, mid, l, r);
    int p2 = query(tree, lazy, 2*node + 1, mid + 1, range_end, l, r);
    return p1+p2;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n, c, height, max_size, i, x, p, q, v, node, range_start, range_end, l, r;
        cin>>n>>c;
        cout<<"1\n";
        long long tree[5*n], lazy[5*n];
        cout<<"2\n";
        for(long long i = 0 ; i < 4*n ; i++)
        {
            tree[i] = 0;
            lazy[i] = 0;
        }
        cout<<"3\n";
        for(i = 0 ; i < c ; i++)
        {
            cin>>x;
            if(x == 0)
            {
                cin>>p>>q>>v;
                update(tree, lazy, 1, 1, n, p, q, v);
            }
            else
            {
                cin>>p>>q;
                cout<<query(tree, lazy, 1, 1, n, p ,q)<<"\n";
            }
        }
        delete(tree);
        delete(lazy);
    }
    return 0;
}

Full text and comments »

  • Vote: I like it
  • -23
  • Vote: I do not like it