fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define f3(i, l, r) for(int i = l; i <= r; i++)
  5. #define fd3(i, l, r) for(int i = l; i >= r; i--)
  6. void openfile(){
  7. 	#define NAME "run"
  8. 	freopen(NAME".INP", "r", stdin);
  9. 	freopen(NAME".OUT", "w", stdout);	
  10. }
  11. const int N = 1e6 + 5;
  12. int a[N];
  13. signed main() {
  14. 	ios_base::sync_with_stdio(0);
  15. 	cin.tie(0);
  16. 	openfile();
  17. 	int n, l, d;
  18. 	cin >> n >> l >> d;
  19. 	f3(i, 1, n) cin >> a[i];
  20. 	deque<int> maxDq, minDq;
  21. 	int i = 1, ans = 0;
  22. 	f3(r, 1, n) {
  23. 		while(!maxDq.empty() && a[maxDq.back()] <= a[r]) {
  24. 			maxDq.pop_back();
  25. 		}
  26. 		maxDq.push_back(r);
  27. 		while(!minDq.empty() && a[minDq.back()] >= a[r]) {
  28. 			minDq.pop_back();
  29. 		}
  30. 		minDq.push_back(r);
  31. 		while(a[maxDq.front()] - a[minDq.front()] > d){
  32. 			if(maxDq.front() == i) maxDq.pop_front();
  33. 			if(minDq.front() == i) minDq.pop_front();
  34. 			++i;
  35. 		}
  36. 		if(r - i >= l){
  37. 			ans += r - i - (l - 1);
  38. 		}
  39. 	}
  40. 	cout << ans;
  41. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1JIpBW
language:
C++14 (gcc 8.3)
created:
11 days 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!