akash2504's blog

By akash2504, 6 years ago, In English,

hello all .. i m trying to the problem http://www.spoj.com/problems/HORRIBLE/ but getting wa again n again... i have used segment trees with lazy propgation .. i have also solved similar problem http://www.spoj.com/problems/LITE/ but i couldnt understand y m gettin wa in this

here is my code....

#include<cstdio>
#define MAX 300000
typedef long long LL;
LL n,m;
struct tree{
LL add;
LL total;
}T[MAX];

void update(LL Node,LL left,LL right,LL i,LL j,LL v){
	if(i==left && j==right){
		T[Node].add += v;
		T[Node].total += (j-i+1)*v;
		return;
	}
	LL mid=(left + right)>>1, L = Node<<1 , R = L+1;
	if(j<=mid)update(L,left,mid,i,j,v);
	else if(i>mid)update(R,mid+1,right,i,j,v);
	else{
		update(L,left,mid,i,mid,v);
		update(R,mid+1,right,mid+1,j,v);
	}
	T[Node].total = T[L].total + T[R].total + T[Node].add*(right-left+1);
	
}
LL query(LL Node,LL left,LL right,LL i,LL j,LL v){
	if(i==left && j==right)return T[Node].total + v*(j-i+1);
	LL mid=(left + right)>>1, L = Node <<1 , R = L+1;
	if(j<=mid) return query(L,left,mid,i,j,v+T[Node].add);
	else if(i>mid)return query(R,mid+1,right,i,j,v+T[Node].add);
	else{
		LL ret =0;
		ret+= query(L,left,mid,i,mid,v+T[Node].add);
		ret+= query(R,mid+1,right,mid+1,j,v+T[Node].add);
		return ret;
	}
	
}

int main(){
LL t;
scanf("%lld",&t);
while(t--){
scanf("%lld %lld",&n,&m);
	for(LL i=0;i<=3*n;i++)
		T[i].total = T[i].add = 0;
while(m--){
	LL q,a,b,k;
	scanf("%lld %lld %lld",&q,&a,&b);
		switch(q){
			case 0:scanf("%lld",&k);
				update(1,0,n-1,a-1,b-1,k);break;
			case 1:printf("%lld\n",query(1,0,n-1,a-1,b-1,0));break;
		}
}
}
return 0;
}

checked on these test cases :

2
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
4 3
0 1 4 1
1 2 2
1 1

o/p

80
508
1
3

as provided in question :P

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like you got WA because of the %lld modifier. It's very unreliable. I replaced it with %I64d and now you get TLE, which is the same I got when I tried to solve the problem...

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Alright.

After learning about lazy propagation, which is new to me, re-coding most of my routines and extensively debugging my code, I managed to get AC with a total runtime of over 8 seconds. Yeah, terribly slow, though it's mainly because of the use of iostream (I couldn't get it accepted using stdio (it's terribly unreliable when it comes to 64-bit integers)).

The first error I see in your code is in the update routine. You have if(i==left && j==right){...}. If the case is that i < left, and then you go to the left child, you call update with parameters L, left, mid, i, mid, v. So i will still be < left, and that subroutine will be skipped. I would replace the logic behind that routine to always let static the values of i and j, and when left >= i && right <= j, update the values of the node and return. And if at any time, left > j || right < i, return.

The same applies to the query routine.

I also changed the update of T[Node].total. As I understood it, lazy propagation works as follows:

  • When you reach the final node of the update routine, you add v to its children's add (T[L].add and T[R].add), and do nothing more.
  • If when you run a query routine, you come across a node with a value of add > 0, you update its total value accordingly, mark its children as needed to be updated (you set T[L].add += T[Node].add, and the same for the right child) and finally set T[Node].add = 0.

I also changed the left and right values of the node. In your code, you dynamically assigned ranges to nodes, and built your tree with a random value of 10^5 * 3. It's always better to build a tree with size 2^x. That way, you'll know that every node has 2 children, and that the range of the first node will be 1 — size / 2.

With those modifications, and a little debugging, your code got accepted too.

Here's the modified version...

#include<iostream>

#define MAX 262145

using namespace std;

typedef long long LL;
LL n,m;
struct tree{
LL add;
LL total;
}T[MAX];

void update(LL Node,LL left,LL right,LL i,LL j,LL v){
    if(left > j || right < i) return;
	if(left >= i && right <= j){
	    if(left != right){
            LL L = Node<<1 , R = L+1;
            T[L].add += v;
            T[R].add += v;
	    }

		T[Node].total += (right-left+1)*v;
		return;
	}

	LL mid=(left + right)>>1, L = Node<<1 , R = L+1;
    update(L,left,mid,i,j,v);
    update(R,mid+1,right,i,j,v);
	T[Node].total += v*(min(right, j)-max(left, i)+1);
}

LL query(LL Node,LL left,LL right,LL i,LL j){
    if(left > j || right < i) return 0;

    if(T[Node].add > 0){
        if(left != right){
            LL L = Node<<1 , R = L+1;
            T[L].add += T[Node].add;
            T[R].add += T[Node].add;
	    }

        T[Node].total += T[Node].add*(right-left+1);
        T[Node].add = 0;
    }

    if(left >= i && right <= j)return T[Node].total;

    LL mid = (right+left)/2, L = Node<<1 , R = L+1;
    LL ret =0;
    ret+= query(L,left,mid,i,j);
    ret+= query(R,mid+1,right,i,j);
    return ret;
}

int main(){
LL t;
cin >> t;
while(t--){
cin >> n >> m;
	for(LL i=0;i<MAX;i++)
		T[i].total = T[i].add = 0;
while(m--){
	LL q,a,b,k;
	cin >> q >> a >> b;
		switch(q){
			case 0:cin >> k;
				update(1,1,MAX/2,a,b,k);break;
			case 1:cout << query(1,1,MAX/2,a,b) << endl;break;
		}
}
}
return 0;
}

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

    thanks a lot!! i think i have to practice more!

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

    Thanks for explanation, it is very helpful. I have one doubt, in update routine you used T[Node].total += v*(min(right, j)-max(left, i)+1) how does it work? and why not used T[Node].total = T[L].total + T[R].total ?

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 6   Vote: I like it 0 Vote: I do not like it

      What it does is increase the total value of the interval by v * (num of elements in interval). The number of elements is min(right, j) — max(left, i) + 1.

      And about the other question, consider this case...

      • Increase elements 1 to 16 by 10.
      • Increase elements 1 to 8 by 5.

      In the first update, the program sets the total variable of the range 1 - 16 to 160. The sub-ranges 1 - 8 and 9 - 16 don't get updated, so they still contain zero. In the second update, the program sets the total variable of the range 1 - 8 to 40 (note that the lazy propagation is done in the queries, but not in the updates), but the range 9 - 16 still contains zero, because it hasn't been lazily updated yet. So if you try to update the range 1 - 16 by doing T[Node].total = T[L].total + T[R].total, you would end up with 40 instead of the wanted 200.

      Furthermore, even if you do the lazy propagation in the update routine as well, in the second update you would set the total variable of the range 1 - 8 to 80 and then increase it by 40, ending up with 120, but the range 9 - 16 will still contain zero, because it's outside the update range. So you will get 120 in 1 - 16 if you do T[Node].total = T[L].total + T[R].total, still not the correct result.

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

    A way to speed this up is to use scanf. Only the output can overflow. Input can be regular int.

    So only that one cout at the end is slow.

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

    hey! can you tell errors in this on as well, i'm getting WA.

    http://ideone.com/arYXRl

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a good tutorial about lazy propagation. Good luck!

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

include

include

using namespace std;

long long segtree[4*100002]; long long lazy[4*100002];

void update(long long node, long long l,long long m,long long a,long long b, long long val) {if(a > b || a > m || b < l) // Current segment is not within range [i, j] return; if(lazy[node]!=0) {segtree[node]+=lazy[node]*(b-a+1); if(a!=b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; } lazy[node]=0; }

if(a >= l && b <= m) { // Segment is fully within range segtree[node] += (val*(b-a+1));

    if(a != b) { // Not leaf node
       lazy[node*2] += val;
       lazy[node*2+1] += val;
    }

       return;
}



//if(m<=(a+b)/2)
  //update(node*2,l,m,a,(a+b)/2,val);
//else if(l>(a+b)/2)
  // update (node*2+1,l,m,(a+b)/2+1,b,val);
//else
    {update(node*2,l,m,a,(a+b)/2,val);
    update(node*2+1,l,m,(a+b)/2+1,b,val);}
    segtree[node]=(segtree[node*2]+segtree[node*2+1]);

}

long long query(long long node,long long l,long long m,long long a,long long b ) { long long q1,q2; if(a > b || a > m || b < l) return 0;

if(lazy[node]!=0)

{segtree[node]+=lazy[node]*(b-a+1); if(a!=b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; } lazy[node]=0; }

if(l<=a&&b<=m)
    return segtree[node];

// if(m<=(a+b)/2) // return query(node*2,l,m,a,(a+b)/2); // else if(l>(a+b)/2) // return query(node*2+1,l,m,(a+b)/2+1,b); //else q1=query(node*2,l,m,a,(a+b)/2); q2=query(node*2+1,l,m,(a+b)/2+1,b);

return (q1+q2);

}

int main() {long long t,n,p,q,v,c,i; char ch; long long g; //build(1,1,n);

cin>>t; while(t--) {memset(segtree,0,400008); memset(lazy,0,400008); cin>>n>>c;

while(c--) {cin>>ch; if(ch=='0') {cin>>p>>q>>v; update(1,p,q,1,n,v);} else if(ch='1') {cin>>p>>q; g=query(1,p,q,1,n); cout<<g<<endl; //cout<<segtree[11].sum<<endl; } } } return 0;}

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting WA, anyone can help out?

#include <cstdio>
#include <cstring>

using namespace std;

long long st[400000];
long long lazy[400000];
int n;

void update(int i, int j, int value, int L=0, int R=n-1, int p=1)
{
    if(lazy[p])
    {
        if(L!=R)
        {
            lazy[p*2]+=lazy[p];
            lazy[p*2+1]+=lazy[p];
        }
        st[p]+=lazy[p]*(R-L+1);
        lazy[p]=0;
    }
    if(i>R || j<L)
        return;
    if(i<=L && j>=R)
    {
        st[p]+=(long long)(R-L+1)*value;
        if(L!=R)
        {
            lazy[p*2]+=value;
            lazy[p*2+1]+=value;
        }
    }
    else
    {
        update(i,j,value,L,(L+R)/2,p*2);
        update(i,j,value,(L+R)/2+1,R,p*2+1);
        st[p]=st[p*2]+st[p*2+1];
    }
}

long long query(int i, int j, int L=0, int R=n-1, int p=1)
{
    if(lazy[p])
    {
        if(L!=R)
        {
            lazy[p*2]+=lazy[p];
            lazy[p*2+1]+=lazy[p];
        }
        st[p]+=lazy[p]*(R-L+1);
        lazy[p]=0;
    }
    if(i>R || j<L)
        return 0;
    if(i<=L && j>=R)
        return st[p];
    return query(i,j,L,(L+R)/2,p*2)+query(i,j,(L+R)/2+1,R,p*2+1);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int q,a,b,c;
        scanf("%d%d",&n,&q);
        memset(lazy,0,sizeof(lazy));
        memset(st,0,sizeof(st));
        while(q--)
        {
            scanf("%d",&a);
            if(a==1)
            {
                scanf("%d%d",&a,&b);
                printf("%I64d\n",query(--a,--b));
            }
            else
            {
                scanf("%d%d%d",&a,&b,&c);
                update(--a,--b,c);
            }
        }
    }
}

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to solve the same problem, using optimized version of ST + LP.

I have tried so many test cases, with boundary cases, all are giving correct answer, 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;
}
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Here's my solution using your approach, Hope it helps, though it's too late....

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef    long long          ll;
    typedef    vector<long long>    vi; 
    typedef    vector<vi>         vvi; 
    typedef    pair<long,long>      ii; 
    #define    sz(a)              long((a).size()) 
    #define    pb                 push_back 
    #define    mp                   make_pair
    #define    all(c)             (c).begin(),(c).end() 
    #define    tr(c,i)            for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
    #define    present(c,x)       ((c).find(x) != (c).end()) 
    #define    cpresent(c,x)      (find(all(c),x) != (c).end())  
    #define    input(v,n)           for(ll i = 0 ; i<n ; i++) cin>>v[i]
    #define    output(v,n)          for(ll i = 0 ; i<n ; i++) cout<<v[i]<<" "
    
    ll t[400010],d[400010],n,h;
    
    void calc(ll p, ll k) 
    {
      if (d[p] == 0) t[p] = t[p<<1] + t[p<<1|1];
      else t[p] = t[p<<1] + t[p<<1|1] + d[p] * k;
    }
    
    void apply(ll p, ll value, ll k) 
    {
      t[p] += value * k;
      if (p < n) d[p] += value;
    
    }
    
    void build(ll l, ll r) 
    {
      ll k = 2;
      for (l += n, r += n-1; l > 1; k <<= 1) 
      {
        l >>= 1, r >>= 1;
        for (ll i = r; i >= l; --i) calc(i, k);
      }
    }
    
    void push(ll l, ll r) 
    {
      ll s = h, k = 1 << (h-1) ;
      for (l += n, r += n-1; s > 0; --s, k >>= 1)
        for (ll i = l >> s; i <= r >> s; ++i) if (d[i] != 0) 
        {
          apply(i<<1, d[i], k);
          apply(i<<1|1, d[i], k);
          d[i] = 0;
        }
    }
    
    void modify(ll l, ll r, ll value) 
    {
      if (value == 0) return;
      push(l, l + 1);
      push(r - 1, r);
    
      ll l0 = l, r0 = r, k = 1;
      for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) 
      {
        if (l&1) apply(l++, value, k);
        if (r&1) apply(--r, value, k);
      }
      build(l0, l0 + 1);
      build(r0 - 1, r0);
    }
    
    ll query(ll l, ll r) {
      
      push(l,l+1);
      push(r - 1,r);
      
      ll res = 0;
      for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l&1) res += t[l++];
        if (r&1) res += t[--r];
      }
      return res;
    }
     
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cout.tie(NULL);
    
      ll tt,q,l,r,inc,c;
      cin>>tt;
    
      while(tt--)
      {
        cin>>n>>c;
        h = log2(n);
        
        memset(t,0,sizeof(t));
        memset(d,0,sizeof(d));
    
        for(ll i=0; i<c; i++)
        {
          cin>>q;
          if(q == 0)
          {
            cin>>l>>r>>inc;
            modify(l-1,r,inc);
          }
          else
          {
            cin>>l>>r;
            ll ans = query(l-1,r);
            cout<<ans<<endl;
          }
        }
    
      }
    }