c++ - Lazy Propagation - HORRIBLE spoj -

-

i attempting problem horrible spoj , here's link: http://www.spoj.com/problems/horrible/ trying teach myself lazy propagation segment tree. following code have written, have tried make concise , clear possible, please let me know if unclear.

#include <cstdio> #include <algorithm> using namespace std;  typedef long long ll;  ll tree[500010]; ll lazy[500010]={};  void buildst(ll a[], ll stidx, ll l, ll r) {     if(l==r)     {         tree[stidx]=a[l];         return;     }     ll left=2*stidx, right=left+1, mid=(l+r)/2;     buildst(a, left, l, mid);     buildst(a, right, mid+1, r);     tree[stidx]=tree[left]+tree[right]; }  void update(ll stidx, ll i, ll j, ll l, ll r, ll val) {     //printf("%lld %lld %lld %lld %lld\n", stidx, i, j, l, r);     if(lazy[stidx]!=0)     {         tree[stidx]+=(l-r+1)*lazy[stidx];         if(l!=r)         {             lazy[2*stidx]+=lazy[stidx];             lazy[2*stidx+1]+=lazy[stidx];         }         lazy[stidx]=0;     }     //printf("1\n");     if(l>r || l>j || r<i)         return;     //printf("1\n");     if(l>=i && r<=j)     {         //printf("%lld\n", stidx);         tree[stidx]+=(r-l+1)*val;         if(l!=r)         {             lazy[2*stidx]+=val;             lazy[2*stidx+1]+=val;         }         return;     }     ll mid=(l+r)/2;     update(2*stidx, i, j, l, mid, val);     update(2*stidx+1, i, j, mid+1, r, val);     tree[stidx]=tree[2*stidx]+tree[2*stidx+1]; }  ll query(ll stidx, ll i, ll j, ll l, ll r) {     if(lazy[stidx]!=0)     {         tree[stidx]+=lazy[stidx]*(r-l+1);         if(l!=r)         {             lazy[2*stidx]+=lazy[stidx];             lazy[2*stidx+1]+=lazy[stidx];         }         lazy[stidx]=0;     }     if(l>r || l>j || r<i)         return 0;     if(l>=i && r<=j)         return tree[stidx];     ll mid=(l+r)/2;     ll q1=query(2*stidx, i, j, l, mid);     ll q2=query(2*stidx+1, i, j, mid+1, r);     return q1+q2; }  ll a[100010];  int main() {     ll t, n, c, type, p, q, v, i;     scanf("%lld", &t);     while(t--)     {         scanf(" %lld %lld", &n, &c);         for(i=0; i<n; ++i)             a[i]=0;         for(i=0; i<4*n; ++i)             lazy[i]=0;         buildst(a, 1, 0, n-1);         while(c--)         {             scanf(" %lld", &type);             if(type==0)             {                 scanf(" %lld %lld %lld", &p, &q, &v);                 update(1, p-1, q-1, 0, n-1, v);                 //for(i=1; i<=15; ++i)                 //  printf("%lld ", tree[i]);                 //printf("\n");              }             if(type==1)             {                 scanf(" %lld %lld", &p, &q);                 printf("%lld\n", query(1, p-1, q-1, 0, n-1));             }         }     }     return 0; }

the sample testcase provided gives correct answer code when submitted, wrong answer message. have checked code lot of times can't find bug.

any appreciated. thanks!

one of error can see in update function

instead of tree[stidx]+=(l-r+1)*lazy[stidx]; should tree[stidx]+=(r-l+1)*lazy[stidx];


Comments

Post a Comment

Popular posts from this blog

python - No exponential form of the z-axis in matplotlib-3D-plots -

-
Image
i have similar problem described in how prevent numbers being changed exponential form in python matplotlib figure : i don't want (in special case) weird scientific formatting of axis. problem different have problem @ z -axis. 2-d plots can use ax.get_yaxis().get_major_formatter().set_useoffset(false) . , there no function ax.get_zaxis() what use format z -axis same way? edit: example: from mpl_toolkits.mplot3d import axes3d import numpy np import sys import matplotlib import matplotlib.pyplot pyplot def func(xi, ti): res = 10e3 + np.cos(ti) * np.sin(xi) return res if __name__ == '__main__': timespacing = 20 timestart = 0 timeend = 1 time = np.linspace(timestart, timeend, timespacing) widthspacing = 50 widthstart = 0 widthend = 3 width = np.linspace(widthstart, widthend, widthspacing) reslist = [] matplotlib.rcparams['legend.fontsize'] = 10 fig = pyplot.figure() ax = fig.gca(projection = '3d...
Read more

php - Best Light server (Linux + Web server + Database) for Raspberry Pi -

-
i install web server database on raspberry pi (little computer). computer has 1gb ram. i want know best combination: linux distribution , web server , dbms run local server multiple users minimal latency, use php on server. , best settings performance , not have bugs (memory usage, disable plugin, disable service, etc)? i thought light debian , lighttpd server , sqlite database. solution? i think lighttpd + sqlite great choice. linux distro, debian @ centos or tiny core linux , although i'm not sure of compatibility pi. obviously, can't go wrong raspbian if want use in production , more stable performance, few more pi's , set them in cluster .
Read more

c# - "Newtonsoft.Json.JsonSerializationException unable to find constructor to use for types" error when deserializing class -

-
i developing app in xamarin android. have splash screen serialize class , pass mainactivity using intent . when try deserialize in mainactivity error message : "serializationexception unable find constructor use types" serialization : void loaddata() { currency currency = new currency(this); intent = new intent(this, typeof(mainactivity)); intent.putextra("currency", newtonsoft.json.jsonconvert.serializeobject(currency)); startactivity(intent); } deserialization : cur = newtonsoft.json.jsonconvert.deserializeobject<currency> (intent.getstringextra("currency")); // error here class constructor : public currency(context context) { thiscontext = context; } i began experiencing problem after added parameter context context constructor. has caused this? how can solve it? possible serialize/deserialize class has parameters? you need have empty constructor in currency class in order deserialize it. ...
Read more