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. //* 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.  
  54.  
  55.  
  56. //* Template 1
  57.  
  58. int consistency2(int n, int k){
  59.  
  60.     unordered_map<int,int> big, small;
  61.     int ans = 0;
  62.     int s = 0, l = 0, e = 0;
  63.  
  64.     while(e<n){
  65.         //* Calculate State
  66.         big[a[e]]++;
  67.         small[a[e]]++;
  68.  
  69.  
  70.         //* Maintain atmost K-1 small window
  71.         while(l<=e && small.size() >= k){
  72.             small[a[l]]--;
  73.             if(small[a[l]] == 0) small.erase(a[l]);
  74.             l++;
  75.         }
  76.  
  77.  
  78.  
  79. 		//* Atmost K big window
  80.  
  81. 		//* Insufficient window => Expand 
  82.         if(big.size() < k){
  83.             e++;
  84.         }
  85.         //* Sufficient window 
  86.         else{
  87.         	//* Invalid window => Keep Shrink Window
  88.             while(s<=e && big.size() > k){
  89.                 big[a[s]]--;
  90.                 if(big[a[s]] == 0) big.erase(a[s]);
  91.                 s++;
  92.             }
  93.  
  94.             //* Valid window => Compute Result && expand 
  95.             //* 	Big window - small window
  96.             ans += (l-s);
  97.             e++;
  98.         }
  99.     }
  100.     return ans;
  101. }
  102.  
  103.  
  104.  
  105.  
  106. //* Template 2
  107.  
  108. int consistency3(int n, int k){
  109.  
  110.     unordered_map<int,int> big, small;
  111.     int ans = 0;
  112.     int s = 0, l = 0, e = 0;
  113.  
  114.     while(e<n){
  115.         //* Calculate State
  116.         big[a[e]]++;
  117.         small[a[e]]++;
  118.  
  119.  
  120.         //* Maintain atmost K-1 small window
  121.         while(l<=e && small.size() >= k){
  122.             small[a[l]]--;
  123.             if(small[a[l]] == 0) small.erase(a[l]);
  124.             l++;
  125.         }
  126.  
  127.  
  128.     	//* Maintain atmost K big window
  129.         while(s<=e && big.size() > k){
  130.             big[a[s]]--;
  131.             if(big[a[s]] == 0) big.erase(a[s]);
  132.             s++;
  133.         }
  134.  
  135.  
  136.         //* Valid window => Compute Result && expand 
  137.     	//* 	Big window - small window
  138.         ans += (l-s);
  139.         e++;
  140.     }
  141.  
  142.     return ans;
  143. }
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150. int consistency4(int n, int k){
  151.  
  152.     unordered_map<int,int> big, small;
  153.     int ans = 0;
  154.  
  155.     for(int j=0, i=0, l=0; j<n; j++){
  156.         big[a[j]]++;
  157.         small[a[j]]++;
  158.  
  159.  
  160.         //* Maintain atmost K-1 small window
  161.         while(l<=j && small.size() >= k){
  162.             small[a[l]]--;
  163.             if(small[a[l]] == 0) small.erase(a[l]);
  164.             l++;
  165.         }
  166.  
  167.  
  168.     	//* Maintain atmost K big window
  169.         while(i<=j && big.size() > k){
  170.             big[a[i]]--;
  171.             if(big[a[i]] == 0) big.erase(a[i]);
  172.             i++;
  173.         }
  174.  
  175.         ans += (l-i);
  176.     }
  177.  
  178.     return ans;
  179. }
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204. int practice(int n, int k){
  205.  
  206. 	return 0;	
  207. }
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216. void solve() {
  217.  
  218. 	int n, k;
  219. 	cin >> n >> k;
  220. 	a.resize(n);
  221. 	for(int i=0; i<n; i++) cin >> a[i];
  222.  
  223. 	cout << consistency1(n, k) << " " << consistency2(n,k) <<  " " << consistency3(n,k) << " " << consistency4(n,k) << endl;
  224.  
  225. 	// cout << consistency1(n, k) << " -> " << practice(n, k) << endl;
  226.  
  227. }
  228.  
  229.  
  230.  
  231.  
  232.  
  233. int32_t main() {
  234.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  235.  
  236.     int t = 1;
  237.     cin >> t;
  238.     while (t--) {
  239.         solve();
  240.     }
  241.  
  242.     return 0;
  243. }
Success #stdin #stdout 0.01s 5308KB
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 7
2 2 2 2
3 3 3 3
https://ideone.com/eH0Vir
language:
C++14 (gcc 8.3)
created:
3 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!