fork(10) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int n, m, t, l, r, x, mark[410000];
  6. long long delta[410000], sum[410000];
  7.  
  8. void read(int &x) {
  9. 	char k;
  10. 	for (k = getchar(); k <= 32; k = getchar());
  11. 	for (x = 0; '0' <= k; k = getchar())	x = x * 10 + k - '0';
  12. }
  13.  
  14. void mkt(int k, int q, int h) {
  15. 	if (q < h) {
  16. 		mkt(k * 2, q, (q + h) / 2);
  17. 		mkt(k * 2 + 1, (q + h) / 2 + 1, h);
  18. 		mark[k] = 0;
  19. 	}else	mark[k] = q;
  20. }
  21.  
  22. long long query(int k, int q, int h, int l, int r) {
  23. 	if (l <= q && h <= r)	return sum[k];
  24. 	if (r <= (q + h) / 2)	return query(k * 2, q, (q + h) / 2, l, r) + 1LL * delta[k] * (r - l + 1);
  25. 	if ((q + h) / 2 < l)	return query(k * 2 + 1, (q + h) / 2 + 1, h, l, r) + 1LL * delta[k] * (r - l + 1);
  26. 	return query(k * 2, q, (q + h) / 2, l, (q + h) / 2) + query(k * 2 + 1, (q + h) / 2 + 1, h, (q + h) / 2 + 1, r) + 1LL * delta[k] * (r - l + 1);
  27. }
  28.  
  29. void Clear(int k, int q, int h) {
  30. 	if (mark[k] > 0) {
  31. 		delta[k] += abs(mark[k] - x);
  32. 		sum[k] += 1LL * abs(mark[k] - x) * (h - q + 1);
  33. 	}else {
  34. 		Clear(k * 2, q, (q + h) / 2);
  35. 		Clear(k * 2 + 1, (q + h) / 2 + 1, h);
  36. 		sum[k] = sum[k * 2] + sum[k * 2 + 1] + 1LL * delta[k] * (h - q + 1);
  37. 	}
  38. 	mark[k] = -1;
  39. }
  40.  
  41. void modify(int k, int q, int h) {
  42. 	if (l <= q && h <= r)	Clear(k, q, h), mark[k] = x;
  43. 	else {
  44. 		if (mark[k] > 0)	mark[k * 2] = mark[k * 2 + 1] = mark[k], mark[k] = 0;
  45. 		if (r <= (q + h) / 2)	modify(k * 2, q, (q + h) / 2);
  46. 		else	if ((q + h) / 2 < l)	modify(k * 2 + 1, (q + h) / 2 + 1, h);
  47. 		else	modify(k * 2, q, (q + h) / 2), modify(k * 2 + 1, (q + h) / 2 + 1, h);
  48. 		mark[k] = 0;
  49. 		sum[k] = sum[k * 2] + sum[k * 2 + 1] + 1LL * delta[k] * (h - q + 1);
  50. 	}
  51. }
  52.  
  53. int main() {
  54. 	read(n); read(m);
  55. 	mkt(1, 1, n);
  56. 	while (m--) {
  57. 		read(t); read(l); read(r);
  58. 		if (t == 1) {
  59. 			read(x);
  60. 			modify(1, 1, n);
  61. 		}else {
  62. 			printf("%I64d\n", query(1, 1, n, l, r));
  63. 		}
  64. 	}
  65. }
  66.  
Time limit exceeded #stdin #stdout 5s 11304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oJsR0W
language:
C++ (gcc 8.3)
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!