fork(1) download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct node
  6. {
  7. 	long long ssum, sum;
  8. 	bool chl0, chl1;
  9. 	long long l0, l1;
  10. };
  11.  
  12. void build (long long *ar, long long lo, long long hi, node *segtree, long long pos)
  13. {
  14. 	if(lo == hi)
  15. 	{
  16. 		segtree[pos].ssum = ar[lo] * ar[lo];
  17. 		segtree[pos].sum = ar[lo];
  18.  
  19. 		segtree[pos].l0 = 0;
  20. 		segtree[pos].l1 = 0;
  21.  
  22. 		segtree[pos].chl0 = 0;
  23. 		segtree[pos].chl1 = 0;
  24.  
  25. 		return;
  26. 	}
  27.  
  28. 	long long mid = (lo + hi)/2;
  29.  
  30. 	build(ar, lo, mid, segtree, 2 * pos + 1);
  31. 	build(ar, mid + 1, hi, segtree, 2 * pos + 2);
  32.  
  33. 	segtree[pos].ssum = segtree[2 * pos + 1].ssum + segtree[2 * pos + 2].ssum;
  34. 	segtree[pos].sum = segtree[2 * pos + 1].sum + segtree[2 * pos + 2].sum;
  35.  
  36. 	segtree[pos].l0 = 0;
  37. 	segtree[pos].l1 = 0;
  38.  
  39. 	segtree[pos].chl0 = 0;
  40. 	segtree[pos].chl1 = 0;
  41. }
  42.  
  43. void pro0(long long lo, long long hi, node *segtree, long long pos)
  44. {
  45. 	if(segtree[pos].chl0 != 0)
  46. 	{
  47. 		segtree[pos].ssum = segtree[pos].l0 * segtree[pos].l0 * (hi - lo + 1);
  48. 		segtree[pos].sum = segtree[pos].l0 * (hi - lo + 1);
  49.  
  50. 		if(lo != hi)
  51. 		{
  52. 			segtree[2 * pos + 1].l0 = segtree[pos].l0;
  53. 			segtree[2 * pos + 2].l0 = segtree[pos].l0;
  54.  
  55. 			segtree[2 * pos + 1].chl0 = 1;
  56. 			segtree[2 * pos + 2].chl0 = 1;
  57.  
  58. 			segtree[2 * pos + 1].chl1 = 0;
  59. 			segtree[2 * pos + 2].chl1 = 0;
  60. 		}
  61.  
  62. 		segtree[pos].l0 = 0;
  63. 		segtree[pos].l1 = 0;
  64.  
  65. 		segtree[pos].chl0 = 0;
  66. 		segtree[pos].chl1 = 0;
  67. 	}
  68.  
  69. 	return;
  70. }
  71.  
  72. void pro1(long long lo, long long hi, node *segtree, long long pos)
  73. {
  74. 	if(segtree[pos].chl1 != 0)
  75. 	{
  76. 		segtree[pos].ssum += (hi - lo + 1) * segtree[pos].l1 * segtree[pos].l1 + 2 * segtree[pos].sum * segtree[pos].l1;
  77. 		segtree[pos].sum += (hi - lo + 1) * segtree[pos].l1;
  78.  
  79. 		if(lo != hi)
  80. 		{
  81. 			segtree[2 * pos + 1].l1 += segtree[pos].l1;
  82. 			segtree[2 * pos + 2].l1 += segtree[pos].l1;
  83.  
  84. 			segtree[2 * pos + 1].chl1 = 1;
  85. 			segtree[2 * pos + 2].chl1 = 1;
  86. 		}
  87.  
  88. 		segtree[pos].l1 = 0;
  89. 		segtree[pos].chl1 = 0;
  90. 	}
  91.  
  92. 	return;
  93. }
  94.  
  95. void update0(long long lo, long long hi, node *segtree, long long pos, long long qlo, long long qhi, long long x)
  96. {
  97. 	pro0(lo, hi, segtree, pos);
  98. 	pro1(lo, hi, segtree, pos);
  99.  
  100. 	if(qlo <= lo && qhi >= hi)
  101. 	{
  102. 		segtree[pos].l0 = x;
  103. 		segtree[pos].chl0 = 1;
  104.  
  105. 		pro0(lo, hi, segtree, pos);
  106.  
  107. 		return;
  108. 	}
  109.  
  110. 	if(qlo > hi || qhi < lo)
  111. 	{
  112. 		return;
  113. 	}
  114.  
  115. 	long long mid = (lo + hi)/2;
  116.  
  117. 	update0(lo, mid, segtree, 2 * pos + 1, qlo, qhi, x);
  118. 	update0(mid + 1, hi, segtree, 2 * pos + 2, qlo, qhi, x);
  119.  
  120. 	segtree[pos].ssum = segtree[2 * pos + 1].ssum + segtree[2 * pos + 2].ssum;
  121. 	segtree[pos].sum = segtree[2 * pos + 1].sum + segtree[2 * pos + 2].sum;
  122. }
  123.  
  124. void update1(long long lo, long long hi, node *segtree, long long pos, long long qlo, long long qhi, long long x)
  125. {  
  126. 	pro0(lo, hi, segtree, pos);
  127. 	pro1(lo, hi, segtree, pos);
  128.  
  129. 	if(qlo <= lo && qhi >= hi)
  130. 	{
  131. 		segtree[pos].l1 = x;
  132. 		segtree[pos].chl1 = 1;
  133.  
  134. 		pro1(lo, hi, segtree, pos);
  135.  
  136. 		return;
  137. 	}
  138.  
  139. 	if(qlo > hi || qhi < lo)
  140. 	{
  141. 		return;
  142. 	}
  143.  
  144. 	long long mid = (lo + hi)/2;
  145.  
  146. 	update1(lo, mid, segtree, 2 * pos + 1, qlo, qhi, x);
  147. 	update1(mid + 1, hi, segtree, 2 * pos + 2, qlo, qhi, x);
  148.  
  149. 	segtree[pos].ssum = segtree[2 * pos + 1].ssum + segtree[2 * pos + 2].ssum;
  150. 	segtree[pos].sum  = segtree[2 * pos + 1].sum  + segtree[2 * pos + 2].sum;
  151. }
  152.  
  153. long long query(long long lo, long long hi, node *segtree, long long pos, long long qlo, long long qhi)
  154. {
  155. 	pro0(lo, hi, segtree, pos);
  156. 	pro1(lo, hi, segtree, pos);
  157.  
  158. 	if(qlo <= lo && qhi >= hi)
  159. 	{
  160. 		return segtree[pos].ssum;
  161. 	}
  162.  
  163. 	if(qlo > hi || qhi < lo)
  164. 	{
  165. 		return 0;
  166. 	}
  167.  
  168. 	long long mid = (lo + hi)/2;
  169.  
  170. 	long long a = query(lo, mid, segtree, 2 * pos + 1, qlo, qhi);
  171. 	long long b = query(mid + 1, hi, segtree, 2 * pos + 2, qlo, qhi);
  172.  
  173. 	return a + b;
  174. }
  175.  
  176. int main()
  177. {
  178. 	//freopen("in.in", "r", stdin);
  179.  
  180. 	long long t, cs = 1;
  181. 	cin >> t;
  182.  
  183. 	while(t--)
  184. 	{
  185. 		cout << "Case " << cs++ << ":" << endl;
  186. 		long long n, q;
  187. 		cin >> n >> q;
  188.  
  189. 		long long *ar = new long long[n];
  190.  
  191. 		for(long long i = 0 ; i < n ; i++)
  192. 		{
  193. 			cin >> ar[i];
  194. 		}
  195.  
  196. 		node *segtree = new node [4 * n];
  197. 		build(ar, 0, n - 1, segtree, 0);
  198.  
  199. 		while(q--)
  200. 		{
  201. 			long long c, st, end, x;
  202.  
  203. 			cin >> c;
  204.  
  205. 			if(c == 0)
  206. 			{
  207. 				cin >> st >> end >> x;
  208. 				update0(0, n - 1, segtree, 0, st - 1, end - 1, x);
  209. 			}
  210.  
  211. 			else if(c == 1)
  212. 			{
  213. 				cin >> st >> end >> x;
  214. 				update1(0, n - 1, segtree, 0, st - 1, end - 1, x);
  215. 			}
  216.  
  217. 			else
  218. 			{
  219. 				cin >> st >> end;
  220. 				cout << query(0, n - 1, segtree, 0, st - 1, end - 1) << endl;
  221. 			}
  222. 		}
  223.  
  224.  
  225.  
  226. 		delete [] segtree;
  227. 		delete [] ar;
  228. 	}	
  229. }
  230.  
Runtime error #stdin #stdout #stderr 0s 4200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/eTwPd4
language:
C++14 (gcc 8.3)
created:
6 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!