fork(4) download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <string>
  5. #include <iomanip>
  6. #include <iterator>
  7. #include <bitset>
  8. #include <vector>
  9. #include <math.h>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13. #include <list>
  14. #include <time.h>
  15. #include <algorithm>
  16.  
  17. using namespace std;
  18.  
  19. int n, q;
  20. double a[1000000];
  21. double add[1000000];
  22. double mult[1000000];
  23. double t[1000000];
  24.  
  25. void build(int v, int tl, int tr)
  26. {
  27. 	if (tl == tr)
  28. 	{
  29. 		t[v] = a[tl];
  30. 		mult[v] = 1;
  31. 		return;
  32. 	}
  33. 	int tm = (tl + tr) / 2;
  34. 	build(v * 2, tl, tm);
  35. 	build(v * 2 + 1, tm + 1, tr);
  36. 	t[v] = t[v * 2] + t[v * 2 + 1];
  37. 	mult[v] = 1;
  38. }
  39.  
  40. void push(int v, int tl, int tr)
  41. {
  42. 	t[v * 2] *= mult[v];
  43. 	t[v * 2 + 1] *= mult[v];
  44. 	mult[v * 2] *= mult[v];
  45. 	mult[v * 2 + 1] *= mult[v];
  46. 	add[v * 2] *= mult[v];
  47. 	add[v * 2 + 1] *= mult[v];
  48. 	mult[v] = 1;
  49. 	int tm = (tl + tr) / 2;
  50. 	t[v * 2] += (double)(tm - tl + 1)*add[v];
  51. 	t[v * 2 + 1] += (double)(tr - tm)*add[v];
  52. 	add[v * 2] += add[v];
  53. 	add[v * 2 + 1] += add[v];
  54. 	add[v] = 0;
  55. 	t[v] = t[v * 2] + t[v * 2 + 1];
  56. }
  57.  
  58. void update(int v, int tl, int tr, int l, int r, double mult_val, double add_val)
  59. {
  60. 	if (l > r)
  61. 		return;
  62. 	if (tl == l&&tr == r)
  63. 	{
  64. 		t[v] *= mult_val;
  65. 		t[v] += double(tr - tl + 1)*add_val;
  66. 		mult[v] *= mult_val;
  67. 		add[v] *= mult_val;
  68. 		add[v] += add_val;
  69. 		return;
  70. 	}
  71. 	push(v, tl, tr);
  72. 	int tm = (tl + tr) / 2;
  73. 	update(v * 2, tl, tm, l, min(tm, r), mult_val, add_val);
  74. 	update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, mult_val, add_val);
  75. 	t[v] = t[v * 2] + t[v * 2 + 1];
  76. }
  77.  
  78. double get(int v, int tl, int tr, int l, int r)
  79. {
  80. 	if (tl == l&&tr == r)
  81. 		return t[v];
  82. 	if (l > r)
  83. 		return 0;
  84. 	push(v, tl, tr);
  85. 	int tm = (tl + tr) / 2;
  86. 	return get(v * 2, tl, tm, l, min(r, tm)) + get(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r);
  87. }
  88.  
  89. int main()
  90. {
  91. 	ios_base::sync_with_stdio(0);
  92. 	cin >> n >> q;
  93. 	for (int i = 0; i < n; i++)
  94. 		cin >> a[i];
  95. 	build(1, 0, n - 1);
  96. 	while (q--)
  97. 	{
  98. 		int type, l, r;
  99. 		cin >> type >> l >> r;
  100. 		l--;
  101. 		r--;
  102. 		if (type == 1)
  103. 		{
  104. 			int le, ri;
  105. 			cin >> le >> ri;
  106. 			le--;
  107. 			ri--;
  108. 			double avg_val1 = get(1, 0, n - 1, l, r) / double(r - l + 1);
  109. 			double avg_val2 = get(1, 0, n - 1, le, ri) / double(ri - le + 1);
  110. 			update(1, 0, n - 1, l, r, double(r - l) / double(r - l + 1), avg_val2 / double(r - l + 1));
  111. 			update(1, 0, n - 1, le, ri, double(ri - le) / double(ri - le + 1), avg_val1 / double(ri - le + 1));
  112. 		}
  113. 		else
  114. 			printf("%.7f\n", get(1, 0, n - 1, l, r));
  115. 	}
  116. }
Time limit exceeded #stdin #stdout 5s 8384512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nGpGqY
language:
C++14 (gcc 8.3)
created:
6 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!