WA on HORRIBLE SPOJ

Правка en1, от wineColoredDays, 2016-01-02 21:05:22

Guys, i'm getting consistently WA on this problem HORRIBLE . I tried some inputs myself, but they are of no use . please help . Here is my code that uses segment tree + lazy propagation :

` #include <bits/stdc++.h> using namespace std;

typedef long long ll;
const int N = 1e5 + 5;

int n, c;
ll s[4 * N];
ll lazy[4 * N];

void upd(int id,int val, int l, int r){
    s[id] += (long long )(1LL * (r-l+1) * (1LL * val));
    lazy[id] += val;
}

void shift(int id, int l, int r){
    int mid = (l + r) / 2;
    upd(2 * id, lazy[id], l, mid);
    upd(2 * id + 1, lazy[id], mid + 1, r);
    lazy[id] = 0;
}

void increase(int x, int y, int val, int id = 1, int l = 1, int r = n){
    if(r < x or y < l) return;
    if(x <= l and r <= y){
       upd(id, val, l, r); 
       return;
    }
    shift(id, l, r);
    int mid = (l + r) / 2;
    increase(x, y, val, 2 * id, l, mid);
    increase(x, y, val, 2 * id + 1, mid + 1, r);
    s[id] = (s[2 * id] + s[2 * id + 1]);
}

ll query(int x, int y, int id = 1, int l = 1, int r = n){
    if(r < x or y < l) return 0;
    if(x <= l and r <= y){
       return s[id];
    }
    shift(id, l, r);
    int mid = (l + r) / 2;
    return query(x, y, 2 * id, l, mid) + query(x, y, 2 * id + 1, mid + 1, r);
}

int main() {

    int Test; cin >> Test;
    for(int t = 0; t < Test; t++){
       cin >> n >> c;

       for(int i = 0; i < N; i++){
         s[i] = 0;
         lazy[i] = 0;
       }

       for(int i = 0; i < c; i++){
         int type, p, q, v;
         cin >> type;

         if(type == 0){

          cin >> p >> q >> v;
          increase(p, q, v);
         }
         else{

         cin >> p >> q;
          ll ans = query(p, q);
          cout << ans << '\n';

         }
       }
    }
    return 0;
} `

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский wineColoredDays 2016-01-02 21:05:22 2027 Initial revision (published)