fork download
copy 
  1. //Solution by Tima
  2. #include <bits/stdc++.h>
  3.  
  4. #define f first
  5. #define s second
  6. #define ll long long
  7. #define ull unsigned long long
  8. #define mp make_pair
  9. #define pb push_back
  10. #define vi vector <int>
  11. #define ld long double
  12. #define pii pair<int, int>
  13. #define y1 sda
  14.  
  15. using namespace std;    
  16. const int N = int(3e5) + 12, mod = int(1e9)  + 7, K = 450; 
  17.  
  18. ll ans[N], d[K + 5][K + 5];
  19. int n, m, a[N], b[N],c[N], cn, L[N], R[N];
  20. int lastq[N], Nx[N], Pv[N], first[K + 5][K + 5], last[K + 5][K + 5];
  21. int p[N], pn;
  22.  
  23. pair<int, int> A[N], B[N];
  24.  
  25. int nxt[N], prv[N];
  26.  
  27. vector <int> del[N];
  28.  
  29. void calc(int l,int r){
  30. 	pn = 0;
  31.  
  32. 	for(int i = l; i <= r; i++){
  33. 		p[++pn] = a[i];
  34. 	}
  35. 	sort(p + 1, p + pn + 1);
  36. 	pn = unique(p + 1, p + pn + 1) - p - 1;
  37. 	for(int i = l; i <= r; i++){
  38. 		b[i] = lower_bound(p + 1, p + pn + 1, a[i]) - p;	
  39. 		del[b[i]].pb(i);
  40. 	}
  41. 	p[pn + 1] = cn + 1;
  42. 	memset(d, 0, sizeof(d));
  43. 	memset(last, 0, sizeof(last));
  44. 	memset(first, 0, sizeof(first));
  45. 	for(int x = 1, ls; x <= pn; x++){
  46. 		int y = pn;
  47. 		ls = 0;
  48. 		ll cur = 0;
  49. 		for(int i = l; i <= r; i++){
  50. 			if(p[x] <= a[i] && a[i] <= p[y]){
  51. 				nxt[ls] = i;
  52. 				prv[i] = ls;
  53. 				if(ls){
  54. 					cur += abs(a[i] - a[ls]);
  55. 				}	
  56. 				ls = i;
  57. 			}
  58. 		}
  59. 		nxt[ls] = n + 1, prv[n + 1] = ls;
  60. 		d[x][y] = cur;
  61. 		if(ls != 0) {
  62. 			first[x][y] = a[nxt[0]];
  63. 			last[x][y] = a[ls];
  64. 		}
  65. 		while(y > x){
  66. 			for(int i : del[y]){
  67. 				int l = prv[i],r = nxt[i];
  68. 				if(l > 0) cur -= (a[i] - a[l]);
  69. 				if(r <= n) cur -= (a[i] - a[r]);
  70. 				if(l > 0 && r <= n) cur += abs(a[l] - a[r]);
  71. 				nxt[l] = r, prv[r] = l;
  72. 			}
  73. 			y--;
  74. 			d[x][y] = cur;
  75. 			first[x][y] = a[nxt[0]], last[x][y] = a[prv[n + 1]];
  76. 		}
  77. 	}
  78. 	int it = pn + 1;
  79.     for (int i = m; i >= 1; --i) {
  80.         while (it - 1 > 0 && p[it - 1] >= A[i].first) --it;
  81.         Nx[A[i].second] = it;
  82.     }
  83.     it = 0;
  84.     for (int i = 1; i <= m; ++i) {
  85.         while (it + 1 <= pn && p[it + 1] <= B[i].first) ++it;
  86.         Pv[B[i].second] = it;
  87.     }
  88. 	for(int i = 1,x,y; i <= m; i++){
  89. 	    x = Nx[i], y = Pv[i];
  90. 		ans[i] += d[x][y];
  91. 		if(last[x][y] != 0){
  92. 			if(lastq[i] != 0){
  93. 				ans[i] += abs(lastq[i] - first[x][y]);
  94. 			}
  95. 			lastq[i] = last[x][y];
  96. 		}
  97. 	}
  98. 	for(int i = 1; i <= pn; i++) del[i].clear();
  99. }
  100.  
  101. int main () {
  102. 	scanf("%d%d", &n, &m);
  103.  
  104. 	for(int i = 1; i <= n; i++){
  105. 		scanf("%d", &a[i]);
  106. 	}
  107.  
  108. 	for(int i = 1; i <= m; i++){
  109. 		scanf("%d%d", &L[i], &R[i]);
  110. 		A[i] = {L[i], i}, B[i] = {R[i], i};
  111. 	}
  112. 	sort(A + 1, A + m + 1);
  113. 	sort(B + 1, B + m + 1);
  114.  
  115. 	for(int i = 1; i <= n; i += K){
  116. 		calc(i, min(i + K - 1,n));
  117. 	}
  118.  
  119. 	for(int i = 1; i <= m; i++){
  120. 		printf("%lld\n", ans[i]);
  121. 	}
  122.  
  123. return 0;
  124. }
Success #stdin #stdout 0s 14072KB
comments (?)
stdin
copy 
10 10
2 4 7 10 6 8 6 2 6 4
3 4
2 6
3 6
3 4
8 8
1 9
6 10
3 5
4 4
3 8
stdout
copy 
0
14
4
0
0
20
11
0
0
10
https://ideone.com/UTyfd3
language:
C++14 (gcc 8.3)
created:
4 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!