akash2504's blog

By akash2504, 7 years ago, , 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 total;
}T[MAX];

void update(LL Node,LL left,LL right,LL i,LL j,LL v){
if(i==left && j==right){
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;
else{
LL ret =0;
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 spoj, Comments (12)
 » 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...
•  » » thanks a lot!! i think i have to practice more!
•  » » 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 →   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.
•  » » 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.
•  » » hey! can you tell errors in this on as well, i'm getting WA.http://ideone.com/arYXRl
 » Here is a good tutorial about lazy propagation. Good luck!
»
5 years ago, # |
Rev. 2

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.sum<<endl; } } } return 0;}

 » Getting WA, anyone can help out? #include #include using namespace std; long long st; long long lazy; 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=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=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); } } } }
 » 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 #include 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; }
•  » » Here's my solution using your approach, Hope it helps, though it's too late.... #include using namespace std; typedef long long ll; typedef vector vi; typedef vector vvi; typedef pair 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>v[i] #define output(v,n) for(ll i = 0 ; i 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>q; if(q == 0) { cin>>l>>r>>inc; modify(l-1,r,inc); } else { cin>>l>>r; ll ans = query(l-1,r); cout<