fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>
  3. #define SIZE 100005
  4.  
  5.  
  6. struct info
  7. {
  8. 	long long sum;
  9. }tree[4*SIZE],Lazy[4*SIZE];
  10.  
  11. long long gcd(long long a, long long b)
  12. {
  13. 	if (a == 0)
  14. 		return b;
  15.  
  16. 	return gcd(b%a, a);
  17. }
  18.  
  19. void initCase()
  20. {
  21.  
  22. 	for (int i = 0; i<SIZE; i++)
  23. 	{
  24. 		tree[i].sum = 0;
  25. 		Lazy[i].sum = -1;
  26. 	}
  27. }
  28.  
  29. void lazyPropagate(int node, int qs, int qe)
  30. {
  31.  
  32. 	if (qs != qe) //interval node
  33. 	{
  34. 		int left = node * 2;
  35. 		int right = (node * 2) + 1;
  36. 		Lazy[left].sum = Lazy[node].sum;
  37. 		Lazy[right].sum = Lazy[node].sum;
  38. 	}
  39. 	tree[node].sum = (qe - qs + 1)*Lazy[node].sum;
  40. 	Lazy[node].sum = -1;
  41. }
  42.  
  43. void update(int node, int qs, int qe, int start, int end, long long value)
  44. {
  45. 	if (Lazy[node].sum != -1)
  46. 		lazyPropagate(node, qs, qe);
  47.  
  48. 	if (qs > end || qe < start)
  49. 		return;
  50.  
  51. 	else if (qs >= start && qe <= end)
  52. 	{
  53. 		tree[node].sum = (qe - qs + 1)*value; //
  54. 		if (qs != qe)
  55. 		{
  56. 			int left = node * 2;
  57. 			int right = (node * 2) + 1;
  58.  
  59. 			Lazy[left].sum = value;
  60. 			Lazy[right].sum = value;
  61. 		}
  62.  
  63.  
  64. 		return;
  65. 	}
  66.  
  67. 	int left = node * 2;
  68. 	int right = (node * 2) + 1;
  69. 	int mid = (qs + qe) / 2;
  70.  
  71. 	update(left, qs, mid, start, end, value);
  72. 	update(right, mid + 1, qe, start, end, value);
  73.  
  74. 	tree[node].sum = tree[left].sum + tree[right].sum;
  75. }
  76.  
  77. long long query(int node, int qs, int qe, int start, int end)
  78. {
  79. 	if (Lazy[node].sum != -1)
  80. 		lazyPropagate(node, qs, qe);
  81.  
  82. 	if (qs > end || qe < start)
  83. 		return 0;
  84.  
  85. 	else if (qs >= start && qe <= end)
  86. 	{
  87. 		return tree[node].sum;
  88. 	}
  89.  
  90. 	int left = node * 2;
  91. 	int right = (node * 2) + 1;
  92. 	int mid = (qs + qe) / 2;
  93.  
  94.  
  95. 	long long b1 = query(left, qs, mid, start, end);
  96. 	long long b2 = query(right, mid + 1, qe, start, end);
  97.  
  98. 	return b1 + b2;
  99. }
  100.  
  101. int main()
  102. {
  103. 	//freopen("inp.txt", "r", stdin);
  104. 	int tc, cn = 1 , n, q, i, j, v, op;
  105. 	scanf("%d", &tc);
  106. 	while (tc--)
  107. 	{
  108. 		initCase();
  109. 		scanf("%d %d", &n, &q);
  110. 		printf("Case %d:\n", cn++);
  111. 		for (int a = 1; a <= q; a++)
  112. 		{
  113. 			scanf("%d", &op);
  114. 			if (op == 1)
  115. 			{
  116. 				scanf("%d %d %d", &i, &j, &v);
  117. 				update(1, 1, n, i+1, j+1, v);
  118. 			}
  119. 			else if (op == 2)
  120. 			{
  121. 				scanf("%d %d", &i, &j);
  122. 				long long res = query(1, 1, n, i + 1, j + 1);
  123. 				long long totalNum = (j - i + 1);
  124.  
  125. 					if (res % totalNum == 0)
  126. 					printf("%lld\n", res / totalNum);
  127. 				else
  128. 				{
  129. 					//printf("Res: %d\n", res);
  130. 					long long  numerator = res / gcd(res, totalNum);
  131. 					long long denominator = totalNum / gcd(res, totalNum);
  132. 					printf("%lld/%lld\n", numerator, denominator);
  133. 				}
  134.  
  135. 			}
  136. 		}
  137. 	}
  138.  
  139. 	return 0;
  140. }
Success #stdin #stdout 0s 21488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RnGhOS
language:
C++14 (clang 8.0)
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!