fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16.  
  17. vector<int> a;
  18.  
  19.  
  20. //* Template1 for Atmost k (i.e. <= k )
  21.  
  22. void consistency1(int n, int k){
  23.  
  24. 	deque<int> up, down; //* indices
  25.  
  26. 	int s = 0, e = 0;
  27. 	int ans = 0;
  28. 	while(e<n){
  29.  
  30. 		//* Calculate state => invalidate dq
  31. 	    while(!down.empty() && a[e] >  a[down.back()] ){
  32. 	        down.pop_back();
  33. 	    }    
  34. 	    down.push_back(e);	
  35. 	    while(!up.empty() && a[e] < a[up.back()]){
  36. 	        up.pop_back();
  37. 	    }
  38. 	    up.push_back(e);	
  39.  
  40.  
  41. 	    //* Valid window => expand + Compute result
  42. 	    int mini = a[up.front()];
  43. 	    int maxi = a[down.front()];
  44. 	    int diff = maxi - mini;	
  45.  
  46. 	    if(diff * (e-s+1) <= k){
  47. 	        ans += (e-s+1);
  48. 	        e++;
  49. 	    }
  50. 	    else{
  51. 	    	//* Invlaid window => Shrink 
  52. 	        while(s<e){
  53. 	            int maxi = a[down.front()];
  54. 	            int mini = a[up.front()];
  55. 	            int diff = maxi - mini;
  56. 	            if(diff * (e-s+1) <= k) break;	
  57. 	            if(up.front() == s) up.pop_front();
  58. 	            if(down.front() == s) down.pop_front();
  59. 	            s++;
  60. 	        }
  61.  
  62. 	        //* valid window => Compute result
  63. 	        ans += (e-s+1);
  64. 	        e++;
  65. 	    }
  66. 	}
  67.  
  68. 	cout << ans << endl;
  69.  
  70. }
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78. //* Template2 for Atmost k (i.e. <= k )
  79. //* 	(based on Cache Invalidation) 
  80.  
  81.  
  82. void consistency2(int n, int k){
  83.  
  84. 	deque<int> up, down; //* indices
  85.  
  86. 	int ans = 0;
  87. 	int s=0, e=0;
  88. 	while(e<n){
  89. 		//* Calculate State => Invalidate dq
  90. 	    while(!down.empty() && a[e] >  a[down.back()] ){
  91. 	        down.pop_back();
  92. 	    }    
  93. 	    down.push_back(e);	
  94. 	    while(!up.empty() && a[e] < a[up.back()]){
  95. 	        up.pop_back();
  96. 	    }
  97. 	    up.push_back(e);	
  98.  
  99. 	    //* Invalid window => shrink
  100. 	    while(s<e){
  101. 	        int maxi = a[down.front()];
  102. 	        int mini = a[up.front()];
  103. 	        int diff = maxi - mini;
  104. 	        if(diff * (e-s+1) <= k) break;
  105. 	        if(up.front() == s) up.pop_front();
  106. 	        if(down.front() == s) down.pop_front();
  107. 	        s++;
  108. 	    }	
  109.  
  110.  
  111. 	    //* Valid window Guranteed => Compute Result
  112. 	    int mini = a[up.front()];
  113. 	    int maxi = a[down.front()];
  114. 	    int diff = maxi - mini;	
  115. 	    ans += (e-s+1);
  116.  
  117. 	    e++;
  118. 	}
  119.  
  120. 	cout << ans << endl;
  121. }
  122.  
  123.  
  124.  
  125.  
  126.  
  127. void solve() {
  128.  
  129. 	int n, k;
  130. 	cin >> n >> k;
  131. 	a.resize(n);
  132. 	for(int i=0; i<n; i++) cin >> a[i];
  133.  
  134. 	consistency1(n, k);
  135. 	consistency2(n, k);
  136. 	cout << endl;
  137.  
  138. }
  139.  
  140.  
  141.  
  142.  
  143.  
  144. int32_t main() {
  145.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  146.  
  147.     int t = 1;
  148.     cin >> t;
  149.     while (t--) {
  150.         solve();
  151.     }
  152.  
  153.     return 0;
  154. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3
3 4
1 3 2
4 0
5 5 5 5
3 0
1 2 3
stdout
copy 
5
5

10
10

3
3
https://ideone.com/VGMO2I
language:
C++14 (gcc 8.3)
created:
2 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!