SPOJ Horrible Queries

Правка en2, от Sarthak_8, 2016-11-28 11:19:51

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. What is 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];
}

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

Теги spoj, horrible queries

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Sarthak_8 2016-11-29 09:52:03 10 Tiny change: '1];\n}\n\nint query(lon' -> '1];\n}\n\nlong long query(lon'
en3 Английский Sarthak_8 2016-11-28 12:45:28 17 Tiny change: 'ge cases. What is the error' -> 'ge cases. I can't understand the error'
en2 Английский Sarthak_8 2016-11-28 11:19:51 54
en1 Английский Sarthak_8 2016-11-28 11:17:56 3582 Initial revision (published)