fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e6 + 5; 
  12.  
  13. int n, L, D;  
  14. int h[N]; 
  15.  
  16. int f[21][N]; // f[k][i] = max của đoạn bắt đầu từ i và có độ dài 2^k
  17. int g[21][N]; // g[k][i] = min của đoạn bắt đầu từ i và có độ dài 2^k
  18.  
  19. void precompute() {
  20. 	for (int i = 1; i <= n; i++) f[0][i] = g[0][i] = h[i];  
  21.  
  22. 	for (int k = 1; (1 << k) <= n; k++) {
  23. 		for (int i = 1; i + (1 << k) - 1 <= n; i++) {
  24. 			f[k][i] = max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]); 
  25. 			g[k][i] = min(g[k - 1][i], g[k - 1][i + (1 << (k - 1))]); 
  26. 		}
  27. 	}
  28. }
  29.  
  30. int getMax(int l, int r) {
  31. 	int k = log2(r - l + 1); 
  32. 	return max(f[k][l], f[k][r - (1 << k) + 1]); 
  33. }
  34.  
  35. int getMin(int l, int r) {
  36. 	int k = log2(r - l + 1); 
  37. 	return min(g[k][l], g[k][r - (1 << k) + 1]); 
  38. }
  39.  
  40. int main() {
  41. 	ios::sync_with_stdio(false); 
  42. 	cin.tie(nullptr); 	
  43. 	cin >> n >> L >> D; 
  44. 	for (int i = 1; i <= n; i++) cin >> h[i]; 
  45.  
  46. 	precompute();  
  47.  
  48.   	// Khi ta chốt đầu mút l, với r càng lớn thì giá trị max(h[l..r]) - min(h[l..r]) càng lớn
  49. 	// 	   r - l >= L 
  50. 	// <=> r     >= L + l
  51. 	ll ans = 0;   
  52. 	for (int l = 1, r = 0; l <= n; l++) {
  53. 		// r xa nhất thoả mãn max(h[l..r]) - min(h[l..r]) <= D
  54. 		while ((r + 1 <= n) && (getMax(l, r + 1) - getMin(l, r + 1) <= D)) r++; 
  55. 		ans += max(0, r - (L + l) + 1); 
  56. 	}
  57.  
  58. 	cout << ans << '\n'; 
  59. }
Success #stdin #stdout 0.01s 20016KB
comments (?)
stdin
copy 
10 3 4
5 6 9 7 4 3 5 6 8 8
stdout
copy 
5
https://ideone.com/5ZCIhd
language:
C++14 (gcc 8.3)
created:
346 days 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!