Segment Tree + Lazy Propagation .
Difference between en3 and en4, changed 2,153 character(s)
I am trying to solve the following problem: [http://www.spoj.com/problems/HORRIBLE/](http://www.spoj.com/problems/HORRIBLE/)↵

I have tried so many test cases, with boundary cases, and all are giving correct output, I am still getting WA though!↵

Below is my code, any hint?↵


~~~~~↵
#include <cstring>↵
#include <iostream>↵
using namespace std;↵

typedef long long ll;↵

const int N = 1e5;  // limit for array size↵
ll n, h;  // array size↵
ll t[2 * N];↵
ll d[N];↵


void apply(int p, int value, int k) {↵
    t[p] += value * k;↵
    if (p < n) d[p] += value;↵
}↵


void build(int p) {↵
    int k = 1;↵
    while (p > 1) {↵
        p >>= 1;↵
        k <<= 1;↵
        t[p] = t[p<<1] + t[p<<1|1] + k * d[p];↵
    }↵
}↵

void push(int p) {↵
    for (int s = h; s > 0; --s) {↵
        int i = p >> s;↵
        if (d[i] != 0) {↵
            apply(i<<1, d[i], s);↵
            apply(i<<1|1, d[i], s);↵
            d[i] = 0;↵
        }↵
    }↵
}↵


void inc(int l, int r, int value) {↵
    l += n, r += n;↵
    int l0 = l, r0 = r;↵
    int k = 1;↵
    for (; l <= r; l >>= 1, r >>= 1, k <<= 1) {↵
        if (l & 1)      apply(l++, value, k);↵
        if (r % 2 == 0) apply(r--, value, k);↵
    }↵
    build(l0);↵
    build(r0);↵
}↵

ll query(int l, int r) {↵
    l += n, r += n;↵
    push(l);↵
    push(r);↵
    ll res = 0;↵
    for (; l <= r; l >>= 1, r >>= 1) {↵
        if (l & 1)      res += t[l++];↵
        if (r % 2 == 0) res += t[r--];↵
    }↵
    return res;↵
}↵



int main() {↵
    ios::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    ↵
    ll T, C, p, q, v, o;↵
    ↵
    cin >> T;↵
    ↵
    for(int i = 0; i < T; i++) {↵

        cin >> n >> C;↵
        ↵
        h = sizeof(int) * 8 - __builtin_clz(n);↵
        ↵
        memset(t, 0, sizeof(t));↵
        memset(d, 0, sizeof(d));↵
        ↵
        for(int j = 0; j < C; j++) {↵
            cin >> o >> p >> q;↵
            if(o == 0) {↵
                cin >> v;↵
                inc(p - 1, q - 1, v);↵
            } else {↵
                cout << query(p - 1, q - 1) << '\n';↵
            }↵
        }↵
    }↵
    return 0;↵
}↵
~~~~~↵
.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English trainingtmp 2015-11-25 11:19:20 2153
en3 English trainingtmp 2015-10-07 02:33:20 225
en2 English trainingtmp 2015-10-07 02:15:35 86
en1 English trainingtmp 2015-10-07 02:13:56 2110 Initial revision (published)