fork download
copy 
  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. long long int segtree[1000000];// no need of extra space i reduced it
  8. long long int lazy[1000000];
  9. void updatetree(int low,int high,long long int value,int qlow,int qhigh,int pos); // value should be long long
  10. long long int addtree(int low,int high,int qlow,int qhigh,int pos);
  11. int main()
  12.    {
  13.        ios::sync_with_stdio(false);
  14.        int t,b;
  15.        long long int  n,c,p,q,v,i;
  16.        cin>>t;
  17.        while(t--)
  18.        {
  19.                   cin>>n>>c;
  20.            for(i=0;i<1000000;i++)
  21.            {
  22.                lazy[i]=0;
  23.                segtree[i]=0;
  24.            }
  25.  
  26.  
  27.            for(i=0;i<c;i++)
  28.            {
  29.             cin>>b;
  30.             if(b==0)
  31.             {
  32.                 cin>>p>>q>>v;
  33.                updatetree(0,n-1,v,p-1,q-1,0);
  34.             }
  35.            else
  36.             {
  37.                 cin>>p>>q;
  38.  
  39.                 cout<<addtree(0,n-1,p-1,q-1,0)<<"\n";
  40.             }
  41.            }
  42.        }
  43.        return 0;
  44.    }
  45.  
  46.  
  47. void updatetree(int low,int high,long long int value,int qlow,int qhigh,int pos)
  48.    {
  49.  
  50.        if(lazy[pos]!=0)
  51.         {
  52.             segtree[pos]+=(high-low+1)*lazy[pos];// we store sum on segtree so find sum of all element because lazy has value which is to be transfered to all element so multiply with number of element
  53.             if(low!=high)
  54.               {
  55.               lazy[2*pos+1]+=lazy[pos];// do not calculate sum at passing lazy
  56.               lazy[2*pos+2]+=lazy[pos];// lazy is lazy whatever parent had will pass to child
  57.               }
  58.               lazy[pos]=0;
  59.         }
  60.        if(high < qlow||low>high||qhigh<low)// no need of low>high condition becasue input is correct but its OK
  61.         return;
  62.         if(qlow<=low&&qhigh>=high)
  63.         {
  64.             segtree[pos]+=value*(high-low+1);// same here as above find sum
  65.  
  66.             if(low!=high)
  67.             {
  68.                 lazy[2*pos+1]+=value;
  69.                 lazy[2*pos+2]+=value;
  70.             }
  71.           return ;
  72.         }
  73.         //if partial overlaps
  74.         long long int mid;
  75.         mid=(low+high)/2;
  76.         updatetree(low,mid,value,qlow,qhigh,2*pos+1);
  77.         updatetree(mid+1,high,value,qlow,qhigh,2*pos+2); // you were doing it 2+pos+2 instead of 2*pos+2;
  78.         segtree[pos]=(segtree[2*pos+1]+segtree[2*pos+2]);
  79.    }
  80.  
  81. long long int addtree(int low,int high,int qlow,int qhigh,int pos) //same thing here also :)
  82.       {
  83.  
  84.       if(lazy[pos]!=0)
  85.         {
  86.         segtree[pos]+=(high-low+1)*lazy[pos];
  87.         if(low!=high)
  88.          {
  89.           lazy[2*pos+1]+=lazy[pos];
  90.           lazy[2*pos+2]+=lazy[pos];
  91.          }
  92.          lazy[pos]=0;
  93.         }
  94.       if(qlow>high||qhigh<low||high<low||qhigh<qlow)
  95.       return 0;
  96.  
  97.      if(qlow<=low&&qhigh>=high)
  98.      {
  99.          return segtree[pos];
  100.      }
  101.  
  102.     long long int mid=(low+high)/2;
  103.     long long int q,y;
  104.     q=addtree(low,mid,qlow,qhigh,2*pos+1);
  105.     y=addtree(mid+1,high,qlow,qhigh,2*pos+2);
  106.     return q+y;
  107.       }
  108.  
Success #stdin #stdout 0.01s 19080KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/CGJrCK
problem HORRIBLE, based on SPOJ submission 15759983 (C++14), 2015-12-02 10:11:56
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!