wineColoredDays's blog

WA on HORRIBLE SPOJ
By wineColoredDays, history, 9 years ago, In English

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;
} `
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

hello bro..this is my code.. it's in java, so should be more readable ..I got an AC.. https://ideone.com/w48jeU

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your help, but i was expecting someone to find a bug in mine :)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Do you have java implementation of SPOJ MLTQ3 this that got AC. TIA

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use sqrt decomposition to solve this.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
       for(int i = 0; i < N; i++){
         s[i] = 0;
         lazy[i] = 0;
       }

should you have 4 * N here instead?

P.S. please use next time http://ideone.com or any other website to paste your code

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks for your reply cmd . Even after correcting the bug you pointed, i'm getting WA . I will post my codes somewhere else in future thoughh, sorry for that :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      void upd(int id,int val, int l, int r) Because of laziness val can be large, AC after changing to long long.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks a lot , it is very hard to catch such bugs . How much time did it take you, i suck at debugging can you suggest some tips .

        → Reply