fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 450000
  4. #define inf 0x3f3f3f3f
  5. typedef long long ll;
  6. ll tree[mx],lazy[mx];
  7.  
  8. void build_tree(ll node,ll a,ll b){  //node=current node, b-e=current range
  9.         if(a>b) return;  //out of range
  10.         if(a==b){   //Leaf node
  11.             tree[node]=0;  //initialize value
  12.             return;
  13.         }
  14.         ll mid=(a+b)/2;
  15.         ll left=node*2;
  16.         ll right=(node*2)+1;
  17.         build_tree(left,a,mid);   //Init left child
  18.         build_tree(right,mid+1,b); //Init right child
  19.         tree[node]=(tree[left]+tree[right]);  //Init root value
  20. }
  21.  
  22. void update_tree(ll node,ll a,ll b,ll i,ll j,ll value){
  23.  
  24.     if(lazy[node]!=0){  //This node needs to be updated
  25.         tree[node]+=lazy[node];  //update it
  26.         if(a!=b){
  27.             lazy[node*2]+=(lazy[node]/(b-a+1))*(((a+b)/2)-a+1);  //mark child as lazy
  28.             lazy[1+(node*2)]+=(lazy[node]/(b-a+1))*(b-((a+b)/2)); //mark child as lazy
  29.         }
  30.         lazy[node]=0;   //Reset it
  31.     }
  32.  
  33.     if(a>b || a>j || b<i) return; //current segment is not within range
  34.  
  35.     if(a>=i and b<=j){
  36.         tree[node]+=value*(b-a+1);
  37.         if(a!=b) { // Not leaf node
  38. 			ll mid=(a+b)/2;
  39. 			lazy[node*2]+=value*(mid-a+1);
  40. 			lazy[node*2+1]+=value*(b-mid);
  41. 		}
  42. 		return;
  43.     }
  44.  
  45.     update_tree(node*2, a, (a+b)/2,i,j,value); // Updating left child
  46. 	update_tree(1+node*2,1+(a+b)/2,b,i,j,value); // Updating right child
  47.  
  48. 	tree[node]=(tree[node*2]+tree[node*2+1]); // Updating root with max value
  49. }
  50.  
  51. ll query_tree(ll node,ll a,ll b,ll i,ll j){
  52.  
  53.     if(a>b || a>j || b<i) return 0; // Out of range
  54.  
  55.     if(lazy[node]!=0){ // This node needs to be updated
  56. 		tree[node]+=lazy[node]; // Update it
  57.  
  58. 		if(a!=b) {  //not leaf node.mark it's child as lazy
  59. 			lazy[node*2] +=(lazy[node]/(b-a+1))*(((a+b)/2)-a+1); // Mark child as lazy
  60. 			lazy[node*2+1] +=(lazy[node]/(b-a+1))*(b-((a+b)/2)); // Mark child as lazy
  61. 		}
  62. 		lazy[node] = 0; // Reset it
  63. 	}
  64.  
  65. 	if(a>=i && b<=j) // Current segment is totally within range [i, j]
  66. 		return tree[node];
  67.  
  68. 		ll q1=query_tree(node*2,a,(a+b)/2,i,j); // Query left child
  69. 	    ll q2=query_tree(1+node*2,1+(a+b)/2,b,i,j); // Query right child
  70.  
  71. 	    ll res=(q1+q2); // Return final result
  72.  
  73. 	    return res;
  74. }
  75.  
  76. int main()
  77. {
  78.     ll n,tc,m,com,a,b,val;
  79.         scanf("%lld",&tc);
  80.         while(tc--){
  81.         scanf("%lld%lld",&n,&m);
  82.         memset(lazy,0,sizeof(lazy));
  83.         memset(tree,0,sizeof(tree));
  84.         build_tree(1,1,n);
  85.         while(m--){
  86.             scanf("%lld",&com);
  87.             if(com==0){
  88.                 scanf("%lld%lld%lld",&a,&b,&val);
  89.                 update_tree(1,1,n,a,b,val);
  90.             }
  91.             else{
  92.                 scanf("%lld%lld",&a,&b);
  93.                 printf("%lld\n",query_tree(1,1,n,a,b));
  94.             }
  95.         }
  96.     }
  97.     return 0;
  98. }
  99.  
Runtime error #stdin #stdout 0s 22272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XDKu6K
problem HORRIBLE, based on SPOJ submission 19650373 (CPP14), 2017-06-21 03:49:44
language:
C++14 (gcc 8.3)
created:
7 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!