fork download
copy 
  1. #include <ctime>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9.  
  10. inline int read()
  11. {
  12. 	int x = 0; int v = 1, c;
  13. 	while(c = getchar(), c < '0' || c > '9') if(c == '-') v = -1;
  14. 	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  15. 	return x * v;
  16. }
  17.  
  18. template<typename T> inline void write(T x, int ch = 10)
  19. {
  20. 	static int s[20]; int t = 0;
  21. 	if(x < 0) x = -x, putchar('-');
  22. 	if(x == 0) putchar('0');
  23. 	for(s[t++] = ch; x; x /= 10)
  24. 		s[t++] = x % 10 + '0';
  25. 	while(t--) putchar(s[t]);
  26. }
  27.  
  28. const int maxn = 100005;
  29.  
  30. int n, q, a[maxn];
  31. LL sum[maxn << 2], add[maxn << 2];
  32.  
  33. #define lc o << 1
  34. #define rc lc | 1
  35. #define Lc lc, L, M
  36. #define Rc rc, M + 1, R
  37.  
  38. inline void pushdown(int o, int L, int R)
  39. {
  40. 	if(add[o]) {
  41. 		int M = (L + R) >> 1;
  42. 		add[lc] += add[o]; sum[lc] += add[o] * (M - L + 1);
  43. 		add[rc] += add[o]; sum[rc] += add[o] * (R - M);
  44. 		add[o] = 0;
  45. 	}
  46. }
  47.  
  48. inline void maintain(int o)
  49. {
  50. 	sum[o] = sum[lc] + sum[rc];
  51. }
  52.  
  53. void build(int o, int L, int R)
  54. {
  55. 	if(L == R) {
  56. 		sum[o] = a[L];
  57. 	} else {
  58. 		int M = (L + R) >> 1;
  59. 		build(Lc); build(Rc); maintain(o);
  60. 	}
  61. }
  62.  
  63. void update(int o, int L, int R, int ql, int qr, int v)
  64. {
  65. 	if(L == ql && qr == R) {
  66. 		add[o] += v; sum[o] += (LL)v * (R - L + 1);
  67. 	} else {
  68. 		pushdown(o, L, R);
  69. 		int M = (L + R) >> 1;
  70. 		if(qr <= M) {
  71. 			update(Lc, ql, qr, v);
  72. 		} else if(M < ql) {
  73. 			update(Rc, ql, qr, v);
  74. 		} else {
  75. 			update(Lc, ql, M, v);
  76. 			update(Rc, M + 1, qr, v);
  77. 		}
  78. 		maintain(o);
  79. 	}
  80. }
  81.  
  82. LL query(int o, int L, int R, int ql, int qr)
  83. {
  84. 	if(L == ql && qr == R) {
  85. 		return sum[o];
  86. 	} else {
  87. 		pushdown(o, L, R);
  88. 		int M = (L + R) >> 1;
  89. 		if(qr <= M) {
  90. 			return query(Lc, ql, qr);
  91. 		} else if(M < ql) {
  92. 			return query(Rc, ql, qr);
  93. 		} else {
  94. 			return query(Lc, ql, M) + query(Rc, M + 1, qr);
  95. 		}
  96. 	}
  97. }
  98.  
  99. void input()
  100. {
  101. 	n = read(); q = read();
  102. 	for(int i = 1; i <= n; ++i)
  103. 		a[i] = read();
  104. 	build(1, 1, n);
  105. }
  106.  
  107. void solve()
  108. {
  109. 	register int a, b;
  110. 	register char op[2];
  111. 	while(q--) {
  112. 		scanf("%s", op);
  113. 		a = read(), b = read();
  114. 		if(op[0] == 'C') {
  115. 			update(1, 1, n, a, b, read());
  116. 		} else {
  117. 			write(query(1, 1, n, a, b));
  118. 		}
  119. 	}
  120. }
  121.  
  122. int main()
  123. {
  124. #ifndef ONLINE_JUDGE
  125. 	freopen("input.txt", "r", stdin);
  126. 	freopen("output.txt", "w", stdout);
  127. #endif
  128.  
  129. 	input();
  130. 	solve();
  131.  
  132. #ifndef ONLINE_JUDGE
  133. 	fclose(stdin), fclose(stdout);
  134. 	printf("Run Time: %.3fs\n", (double)clock() / CLOCKS_PER_SEC);
  135. #endif
  136. 	return 0;
  137. }
  138.  
Time limit exceeded #stdin #stdout 5s 10056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/a9rFk5
poj3468
language:
C++14 (clang 8.0)
created:
9 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!