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. 	//* up => [1 , 2 , 4 , ... ] => mini = up.front()
  25. 	//* down => [ 5 , 3, 2 ... ] => maxi = down.front()
  26. 	deque<int> up, down; //* indices
  27.  
  28. 	int s = 0, e = 0;
  29. 	int ans = 0;
  30. 	while(e<n){
  31.  
  32. 		//* Calculate state => invalidate dq
  33. 	    while(!down.empty() && a[e] >  a[down.back()] ){
  34. 	        down.pop_back();
  35. 	    }    
  36. 	    down.push_back(e);	
  37. 	    while(!up.empty() && a[e] < a[up.back()]){
  38. 	        up.pop_back();
  39. 	    }
  40. 	    up.push_back(e);	
  41.  
  42.  
  43. 	    //* Valid window => expand + Compute result
  44. 	    long long mini = a[up.front()];
  45. 	    long long maxi = a[down.front()];
  46.  
  47. 	    if( (maxi-mini) * (e-s+1) <= k){
  48. 	        ans += (e-s+1);
  49. 	        e++;
  50. 	    }
  51. 	    else{
  52. 	    	//* Invlaid window => Shrink 
  53. 	        while(s<e){
  54. 	            long long maxi = a[down.front()];
  55. 	            long long mini = a[up.front()];
  56.  
  57. 	            if((maxi-mini) * (e-s+1) <= k) break;	
  58.  
  59. 	            if(up.front() == s) up.pop_front();
  60. 	            if(down.front() == s) down.pop_front();
  61. 	            s++;
  62. 	        }
  63.  
  64. 	        //* valid window => Compute result
  65. 	        ans += (e-s+1);
  66. 	        e++;
  67. 	    }
  68. 	}
  69.  
  70. 	cout << ans << endl;
  71.  
  72. }
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80. //* Template2 for Atmost k (i.e. <= k )
  81. //* 	(based on Cache Invalidation) 
  82.  
  83.  
  84. void consistency2(int n, int k){
  85.  
  86. 	deque<int> up, down; //* indices
  87.  
  88. 	int ans = 0;
  89. 	int s=0, e=0;
  90. 	while(e<n){
  91. 		//* Calculate State => Invalidate dq
  92. 	    while(!down.empty() && a[e] >  a[down.back()] ){
  93. 	        down.pop_back();
  94. 	    }    
  95. 	    down.push_back(e);	
  96. 	    while(!up.empty() && a[e] < a[up.back()]){
  97. 	        up.pop_back();
  98. 	    }
  99. 	    up.push_back(e);	
  100.  
  101. 	    //* Invalid window => shrink
  102. 	    while(s<e){
  103. 	        long long maxi = a[down.front()];
  104. 	        long long mini = a[up.front()];
  105.  
  106. 	        if( (maxi-mini) * (e-s+1) <= k) break;
  107.  
  108. 	        if(up.front() == s) up.pop_front();
  109. 	        if(down.front() == s) down.pop_front();
  110. 	        s++;
  111. 	    }	
  112.  
  113.  
  114. 	    //* Valid window Guranteed => Compute Result
  115. 	    ans += (e-s+1);
  116. 	    e++;
  117. 	}
  118.  
  119. 	cout << ans << endl;
  120. }
  121.  
  122.  
  123.  
  124.  
  125.  
  126. void solve() {
  127.  
  128. 	int n, k;
  129. 	cin >> n >> k;
  130. 	a.resize(n);
  131. 	for(int i=0; i<n; i++) cin >> a[i];
  132.  
  133. 	consistency1(n, k);
  134. 	consistency2(n, k);
  135. 	cout << endl;
  136.  
  137. }
  138.  
  139.  
  140.  
  141.  
  142.  
  143. int32_t main() {
  144.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  145.  
  146.     int t = 1;
  147.     cin >> t;
  148.     while (t--) {
  149.         solve();
  150.     }
  151.  
  152.     return 0;
  153. }
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/IUr93g
language:
C++14 (gcc 8.3)
created:
6 hours 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!