fork(1) download
copy 
  1. //JUST THE HORRIBLE PART
  2.  
  3. #include<cstdio>
  4. #include<iostream>
  5. #include<string>
  6. #define M 1000000
  7. typedef long long LL;
  8. using namespace std;
  9.  
  10. LL  tree[4*M],lazy[4*M];
  11.  
  12. void buildtree(LL node,LL a,LL b)
  13. {
  14. 	if(a>b)return ;
  15. 	if(a==b)//leaf nodes
  16. 	{
  17. 		tree[node]=0;return;
  18. 		lazy[node]=0;
  19. 	}
  20. 	LL mid=(a+b)/2;
  21. 	buildtree(2*node,a,mid);
  22. 	buildtree(2*node+1,mid+1,b);
  23.  
  24. 	tree[node]=0;
  25. 	lazy[node]=0;
  26. 	return;
  27. }
  28.  
  29. void up(LL node,LL a,LL b,LL i,LL j,LL val)
  30. {
  31.  
  32. 	if(a>b||b<i||a>j){return ;}
  33.  
  34.  
  35. 	if(a>=i&&b<=j)
  36. 	{
  37.       // printf("mayank node %d  a  %d  b    %d    i    %d  j   %d   %d    %d\n",node,a,b,i,j,tree[node],lazy[node]);
  38. 		tree[node]+=val*(b-a+1);
  39.  
  40.  
  41. 		if(a!=b)
  42. 		{
  43. 			lazy[2*node]+=val;
  44. 			lazy[2*node+1]+=val;
  45.  
  46. 		}
  47. 		return ;
  48. 	}
  49.  
  50. 	LL mid=(a+b)/2;
  51. 	up(2*node,a,mid,i,j,val);
  52. 	up(2*node+1,mid+1,b,i,j,val);
  53.  
  54.     tree[node]+=val*(min(b,j)-max(a,i)+1);//the value that need to be changed
  55.   //  printf("vikash node %d  a  %d  b    %d    i    %d  j   %d   %d  \n",node,a,b,i,j,tree[node]);
  56.    //  printf("%d  %d   %d  %d  %d   %d  %d   %d\n",node,a,b,i,j,min(b,j),max(a,i),tree[node]);
  57.  
  58.    //  printf("sonu  %lld   %lld    %lld     %lld\n",node,tree[node],tree[2*node],tree[2*node+1]);
  59.  
  60. 	return ;
  61. }
  62.  
  63. LL  query(LL node,LL a,LL b,LL  i,LL  j)
  64. {
  65. //    printf("node %d  a  %d  b    %d    i    %d  j   %d\n",node,a,b,i,j);
  66. //	system("pause");
  67.  
  68. 	if(a>b||a>j||b<i)return 0;
  69. 	if(lazy[node]!=0)
  70. 	{
  71.     //    printf("tree[node]     %d   node    %d\n",node,lazy[node]);
  72. 		tree[node]+=lazy[node]*(b-a+1);
  73. 		if(a!=b)
  74. 		{
  75. 			lazy[2*node]+=lazy[node];
  76. 			lazy[2*node+1]+=lazy[node];
  77. 		}
  78. 		lazy[node]=0;
  79.    }
  80.    if(a>=i&&b<=j)
  81.    {
  82. 		//tree[node]=tree[node]+lazy[2*node]+lazy[2*node+1];
  83. 		return tree[node];
  84.    }
  85.  
  86.    LL mid=(a+b)/2;
  87.    LL  p,q,res;
  88.    p=query(2*node,a,mid,i,j);
  89.    q=query(2*node+1,mid+1,b,i,j);
  90.    //printf("p   %d q   %d  node  %d\n",p,q,node);
  91.    res=p+q;
  92.   //printf("node   %d  p  %d  q   %d      res  %d\n",node,p,q,res);
  93.    return res;
  94. }
  95.  
  96.  
  97.  
  98. int main()
  99. {
  100. 	LL  t;
  101. 	scanf("%lld",&t);
  102. 	while(t--)
  103. 	{
  104. 	  LL	 n,q;
  105. 		scanf("%lld%lld",&n,&q);
  106. 		buildtree(1,1,n);
  107. 		//memset(lazy,0,sizeof(lazy));
  108. 		//for(int i=1;i<=20;i++)printf("%d  %d\n",i,tree[i]);
  109. 	//	system("pause");
  110. 		while(q--)
  111. 		{
  112.  
  113. 		LL  a,p,q,val;
  114. 		scanf("%lld",&a);
  115. 		if(a==0)
  116. 		{
  117. 			scanf("%lld%lld%lld",&p,&q,&val);
  118. 			up(1,1,n,p,q,val);
  119. 		}
  120. 		else
  121. 		{
  122. 			scanf("%lld%lld",&p,&q);
  123. 			LL z=query(1,1,n,p,q);
  124. 			printf("%lld\n",z);
  125. 		}
  126. 	//	for(int i=1;i<=20;i++)printf("%d  %lld    %lld\n",i,tree[i],lazy[i]);
  127.    //
  128. 	    }
  129. 	}
  130. 	return 0;
  131. }
  132.  
  133.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:3:17: fatal error: cstdio: No such file or directory
 #include<cstdio>
                 ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/HEmQXl
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

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!