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.  
  21. //* Template1 for Atmost k (i.e. <= k )
  22.  
  23. //* Using Ordered Set 
  24.  
  25. int consistency1(int n, int k){
  26.  
  27. 	set<pair<int,int>> st;
  28.  
  29. 	int s = 0, e = 0;
  30. 	int ans = 0;
  31. 	while(e<n){
  32. 		st.insert({a[e], e});
  33.  
  34. 	    //* Valid window => expand + Compute result
  35. 	    if( (  (*st.rbegin()).first -  (*st.begin()).first  ) * (e-s+1) <= k){
  36. 	        ans += (e-s+1);
  37. 	        e++;
  38. 	    }
  39. 	    else{
  40. 	    	//* Invlaid window => Shrink 
  41. 	        while(s<=e &&  ( (*st.rbegin()).first - (*st.begin()).first ) * (e-s+1) > k ){
  42. 				st.erase({a[s], s});	            
  43. 	            s++;
  44. 	        }
  45.  
  46. 	        //* valid window => Compute result
  47. 	        ans += (e-s+1);
  48. 	        e++;
  49. 	    }
  50. 	}
  51.  
  52. 	return ans;
  53.  
  54. }
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61. //* Template1 for Atmost k (i.e. <= k )
  62.  
  63. int consistency2(int n, int k){
  64.  
  65. 	//* up => [1 , 2 , 4 , ... ] => mini = up.front()
  66. 	//* down => [ 5 , 3, 2 ... ] => maxi = down.front()
  67. 	deque<int> up, down; //* indices
  68.  
  69. 	int s = 0, e = 0;
  70. 	int ans = 0;
  71. 	while(e<n){
  72.  
  73. 		//* Calculate state => invalidate dq
  74. 	    while(!down.empty() && a[e] >  a[down.back()] ){
  75. 	        down.pop_back();
  76. 	    }    
  77. 	    down.push_back(e);	
  78. 	    while(!up.empty() && a[e] < a[up.back()]){
  79. 	        up.pop_back();
  80. 	    }
  81. 	    up.push_back(e);	
  82.  
  83.  
  84. 	    //* Valid window => expand + Compute result
  85. 	    long long mini = a[up.front()];
  86. 	    long long maxi = a[down.front()];
  87.  
  88. 	    if( (maxi-mini) * (e-s+1) <= k){
  89. 	        ans += (e-s+1);
  90. 	        e++;
  91. 	    }
  92. 	    else{
  93. 	    	//* Invlaid window => Shrink 
  94. 	        while(s<=e){
  95. 	            long long maxi = a[down.front()];
  96. 	            long long mini = a[up.front()];
  97.  
  98. 	            if((maxi-mini) * (e-s+1) <= k) break;	
  99.  
  100. 	            if(up.front() == s) up.pop_front();
  101. 	            if(down.front() == s) down.pop_front();
  102. 	            s++;
  103. 	        }
  104.  
  105. 	        //* valid window => Compute result
  106. 	        ans += (e-s+1);
  107. 	        e++;
  108. 	    }
  109. 	}
  110.  
  111. 	return ans;
  112.  
  113. }
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121. //* Template2 for Atmost k (i.e. <= k )
  122. //* 	(based on Cache Invalidation) 
  123.  
  124.  
  125. int consistency3(int n, int k){
  126.  
  127. 	deque<int> up, down; //* indices
  128.  
  129. 	int ans = 0;
  130. 	int s=0, e=0;
  131. 	while(e<n){
  132. 		//* Calculate State => Invalidate dq
  133. 	    while(!down.empty() && a[e] >  a[down.back()] ){
  134. 	        down.pop_back();
  135. 	    }    
  136. 	    down.push_back(e);	
  137. 	    while(!up.empty() && a[e] < a[up.back()]){
  138. 	        up.pop_back();
  139. 	    }
  140. 	    up.push_back(e);	
  141.  
  142. 	    //* Invalid window => shrink
  143. 	    while(s<=e){
  144. 	        long long maxi = a[down.front()];
  145. 	        long long mini = a[up.front()];
  146.  
  147. 	        if( (maxi-mini) * (e-s+1) <= k) break;
  148.  
  149. 	        if(up.front() == s) up.pop_front();
  150. 	        if(down.front() == s) down.pop_front();
  151. 	        s++;
  152. 	    }	
  153.  
  154.  
  155. 	    //* Valid window Guranteed => Compute Result
  156. 	    ans += (e-s+1);
  157. 	    e++;
  158. 	}
  159.  
  160. 	return ans;
  161. }
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175. int practice(int n, int k){
  176.  
  177. 	int ans = 0;
  178.  
  179.  
  180. 	return ans;
  181. }
  182.  
  183.  
  184.  
  185.  
  186. void solve() {
  187.  
  188. 	int n, k;
  189. 	cin >> n >> k;
  190. 	a.resize(n);
  191. 	for(int i=0; i<n; i++) cin >> a[i];
  192.  
  193. 	cout << consistency1(n, k) << " " << consistency2(n, k) << " " << consistency3(n, k) << endl;
  194. 	// cout << consistency1(n, k) << " " << practice(n, k) << endl;
  195.  
  196. }
  197.  
  198.  
  199.  
  200.  
  201.  
  202. int32_t main() {
  203.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  204.  
  205.     int t = 1;
  206.     cin >> t;
  207.     while (t--) {
  208.         solve();
  209.     }
  210.  
  211.     return 0;
  212. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3
3 4
1 3 2
4 0
5 5 5 5
3 0
1 2 3
stdout
copy 
5 5 5
10 10 10
3 3 3
https://ideone.com/uwXhBS
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!