I am trying to solve the following problem: [http://www.spoj.com/problems/HORRIBLE/](http://www.spoj.com/problems/HORRIBLE/)↵
↵
I have tried many possible test cases and my code works fine. Although my code is working fine for all test cases I have tried, I am still getting WA!↵
↵
Below is my code, any hint?↵
↵
↵
~~~~~↵
#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);↵
↵
for(int j = 0; j < n; j++) {↵
t[j + n] = 0;↵
d[j] = 0;↵
}↵
↵
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;↵
}↵
~~~~~↵
↵
↵
↵
Below is my code, any hint?↵
↵
↵
~~~~~↵
#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);↵
↵
for(int j = 0; j < n; j++) {↵
t[j + n] = 0;↵
d[j] = 0;↵
}↵
↵
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;↵
}↵
~~~~~↵
↵
