fork(1) 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. //* Count of Exactly k = (Atmost k ) - (Atmost k-1 )
  20.  
  21. int atmostK(int n, int k){
  22.     unordered_map<int,int> mp;
  23.     int ans = 0;
  24.     int s = 0, e = 0;
  25.     while(e<n){
  26.         mp[a[e]]++;
  27.         if(mp.size() <= k){
  28.             ans += (e-s+1);
  29.             e++;
  30.         }
  31.         else{
  32.             while(s<=e && mp.size() > k){
  33.                 mp[a[s]]--;
  34.                 if(mp[a[s]] == 0) mp.erase(a[s]);
  35.                 s++;
  36.             }
  37.             ans += (e-s+1);
  38.             e++;
  39.         }
  40.     }
  41.     return ans;
  42. }
  43.  
  44. int consistency1(int n, int k){
  45.  
  46. 	return atmostK(n, k) - atmostK(n, k-1);
  47.  
  48. }
  49.  
  50.  
  51.  
  52.  
  53. //* Template 1
  54.  
  55. int consistency2(int n, int k){
  56.  
  57.     unordered_map<int,int> big, small;
  58.     int ans = 0;
  59.     int s = 0, l = 0, e = 0;
  60.  
  61.     while(e<n){
  62.         //* Calculate State
  63.         big[a[e]]++;
  64.         small[a[e]]++;
  65.  
  66.         //* Invalid Small window => Shrink 
  67.         while(l<=e && small.size() >= k){
  68.             small[a[l]]--;
  69.             if(small[a[l]] == 0) small.erase(a[l]);
  70.             l++;
  71.         }
  72.  
  73. 		//* Insufficient Big window => Expand Window
  74.         if(big.size() < k){
  75.             e++;
  76.         }
  77.         //* Valid Big window =>  Compute result + Expand window
  78.         else if(big.size() == k){
  79.             ans += (l-s);
  80.             e++;
  81.         }
  82.         else{
  83.         	//* Invalid Big Window => Shrink window
  84.             while(s<=e && big.size() > k){
  85.                 big[a[s]]--;
  86.                 if(big[a[s]] == 0) big.erase(a[s]);
  87.                 s++;
  88.             }
  89.             //* Valid Big window => Compute Result && Expand
  90.             ans += (l-s);
  91.             e++;
  92.         }
  93.     }
  94.     return ans;
  95. }
  96.  
  97.  
  98.  
  99.  
  100. //* Template 2
  101.  
  102. int consistency3(int n, int k){
  103.  
  104.     unordered_map<int,int> big, small;
  105.     int ans = 0;
  106.     int s = 0, l = 0, e = 0;
  107.  
  108.     while(e<n){
  109.         //* Calculate State
  110.         big[a[e]]++;
  111.         small[a[e]]++;
  112.  
  113.         //* Invalid Small window => Shrink 
  114.         while(l<=e && small.size() >= k){
  115.             small[a[l]]--;
  116.             if(small[a[l]] == 0) small.erase(a[l]);
  117.             l++;
  118.         }
  119.  
  120. 		//* Insufficient Big window => Expand Window
  121.         if(big.size() < k){
  122.             e++;
  123.         }
  124.         else{
  125.         	//* Invalid Big Window => Shrink window (cache invalidation)
  126.             while(s<=e && big.size() > k){
  127.                 big[a[s]]--;
  128.                 if(big[a[s]] == 0) big.erase(a[s]);
  129.                 s++;
  130.             }
  131.             //* Valid Big window => Compute Result && Expand
  132.             ans += (l-s);
  133.             e++;
  134.         }
  135.     }
  136.     return ans;
  137. }
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147. int practice(int n, int k){
  148.  
  149. 	return 0;	
  150. }
  151.  
  152.  
  153.  
  154.  
  155. void solve() {
  156.  
  157. 	int n, k;
  158. 	cin >> n >> k;
  159. 	a.resize(n);
  160. 	for(int i=0; i<n; i++) cin >> a[i];
  161.  
  162. 	cout << consistency1(n, k) << " " << consistency2(n,k) <<  " " << consistency2(n,k) << endl;
  163.  
  164. 	// cout << consistency1(n, k) << " -> " << practice(n, k) << endl;
  165.  
  166. }
  167.  
  168.  
  169.  
  170.  
  171.  
  172. int32_t main() {
  173.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  174.  
  175.     int t = 1;
  176.     cin >> t;
  177.     while (t--) {
  178.         solve();
  179.     }
  180.  
  181.     return 0;
  182. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
5 2
1 2 1 2 3
2 1
1 2
5 3
1 2 1 3 4
stdout
copy 
7 7 7
2 2 2
3 3 3
https://ideone.com/cxN1bw
language:
C++14 (gcc 8.3)
created:
7 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!