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. //* O(n*n*10)
  20.  
  21. void bruteforce(int n, int k){
  22.  
  23. 	int ans = 0;
  24. 	for(int i=0; i<n; i++){
  25. 		vector<int> mp(10, 0);
  26. 		for(int j=i; j<n; j++){
  27. 			mp[a[j]]++;
  28.  
  29. 			bool isAllK = true;
  30. 			for(int l=0; l<=9; l++){
  31. 				if(mp[l] == 0) continue;
  32. 				if(mp[l] != k){
  33. 					isAllK = false;
  34. 					break;
  35. 				}
  36. 			}
  37. 			if(isAllK) ans++;
  38. 		}
  39. 	}
  40.  
  41. 	cout << ans << endl;
  42. }
  43.  
  44.  
  45.  
  46. //* T.C. : O(10 * n)
  47.  
  48.  
  49. void consistency(int n, int k){
  50. 	int ans = 0;
  51. 	for(int i=1; i<=10; i++){
  52. 		int m = i*k;
  53.  
  54. 		unordered_map<int,int> mp;
  55.  
  56. 		int s=0, e=0;
  57. 		while(e<n){
  58. 			mp[a[e]]++;
  59. 			if(e-s+1 < m){
  60. 				e++;	
  61. 			}
  62. 			else{
  63.  
  64. 				//* Valid window : where distinct eles == m/2
  65. 				//* Eg : [1, 1, 3, 2, 3, 2] => mp = 3 == 6/2
  66. 				if(mp.size()*2 == m) ans++;
  67.  
  68. 				mp[a[s]]--;
  69. 				if(mp[a[s]] == 0) mp.erase(a[s]);
  70. 				s++;
  71. 				e++;
  72. 			}
  73. 		}
  74.  
  75. 	}
  76.  
  77. 	cout << ans << endl;
  78. }
  79.  
  80.  
  81. void solve() {
  82.  
  83. 	int n, k;
  84. 	cin >> n >> k;
  85. 	a.resize(n);
  86. 	for(int i=0; i<n; i++) cin>> a[i];
  87.  
  88. 	bruteforce(n, k);
  89. 	consistency(n, k);
  90.  
  91. }
  92.  
  93.  
  94.  
  95.  
  96.  
  97. int32_t main() {
  98.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  99.  
  100.     int t = 1;
  101.     cin >> t;
  102.     while (t--) {
  103.         solve();
  104.     }
  105.  
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
2
6 2
1 1 0 0 2 2
7 2
1 1 0 2 0 2 1
stdout
copy 
6
6
4
4
https://ideone.com/xofjgo
language:
C++14 (gcc 8.3)
created:
1 day 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!