fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29. string a;
  30.  
  31. //* Count of Exactly k = (Atmost k ) - (Atmost k-1 )
  32.  
  33. int atmostK(int n, int k){
  34.  
  35. 	vector<int> mp(26);
  36. 	int size = 0;
  37.  
  38. 	int ans = 0;
  39. 	int s = 0, e = 0;
  40.  
  41. 	while(e<n){
  42. 	    mp[a[e]-'a']++;
  43. 	    if(mp[a[e]-'a'] == 1) size++;
  44.  
  45. 	    if(size < k){
  46. 	    	ans += (e-s+1);
  47. 	        e++;
  48. 	    }
  49. 	    else{
  50. 	        while(s<=e && size > k){
  51. 	            mp[a[s]-'a']--;
  52. 	            if(mp[a[s] - 'a'] == 0) size--;
  53. 	            s++;
  54. 	        }
  55. 	        ans += (e-s+1);
  56. 	        e++;
  57. 	    }
  58. 	}
  59.  
  60. 	return ans;
  61. }
  62.  
  63. int consistency1(int n, int k){
  64.  
  65. 	return atmostK(n, k) - atmostK(n, k-1);
  66.  
  67. }
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75. //* Template 1
  76.  
  77.  
  78. int consistency2(int n, int k){
  79.  
  80. 	vector<int> big(26), small(26);
  81. 	int bigSize = 0, smallSize = 0;
  82.  
  83. 	int ans = 0;
  84. 	int s = 0, e = 0;
  85. 	int l = 0;
  86.  
  87. 	while(e<n){
  88.  
  89. 	    big[a[e]-'a']++;
  90. 	    if(big[a[e]-'a'] == 1) bigSize++;
  91.  
  92. 	    small[a[e]-'a']++;
  93. 	    if(small[a[e]-'a'] == 1) smallSize++;
  94.  
  95. 	    while(l<=e && smallSize >= k){
  96. 	        small[a[l]-'a']--;
  97. 	        if(small[a[l]-'a'] == 0) smallSize--;
  98. 	        l++;
  99. 	    }
  100.  
  101. 	    if(bigSize < k){
  102. 	        e++;
  103. 	    }
  104. 	    else{
  105. 	        while(s<=e && bigSize > k){
  106. 	            big[a[s]-'a']--;
  107. 	            if(big[a[s] - 'a'] == 0) bigSize--;
  108. 	            s++;
  109. 	        }
  110. 	        ans += (l-s);
  111. 	        e++;
  112. 	    }
  113. 	}
  114.  
  115. 	return ans;
  116.  
  117. }
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125. //* Template 2
  126. int consistency3(int n, int k){
  127.  
  128.     vector<int> big(26), sm(26);
  129.     int bigSz = 0, smSz = 0;
  130.  
  131.     int ans = 0;
  132.  
  133.     for(int j=0, i=0, l=0; j<n; j++){
  134.  
  135.         big[a[j]-'a']++;
  136.         if(big[a[j] - 'a'] == 1) bigSz++;
  137.  
  138.         sm[a[j]-'a']++;
  139.         if(sm[a[j] - 'a'] == 1) smSz++;
  140.  
  141.  
  142.         while(l<=j && smSz >= k){
  143.             sm[a[l]-'a']--;
  144.             if(sm[a[l] - 'a'] == 0) smSz--;
  145.             l++;
  146.         }
  147.  
  148.         while(i<=j && bigSz > k){
  149.             big[a[i] - 'a']--;
  150.             if(big[a[i] - 'a'] == 0) bigSz--;
  151.             i++;
  152.         }
  153.  
  154.         ans += l-i;
  155.  
  156.     }
  157.     return ans;
  158. }
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175. int practice(int n, int k){
  176.  
  177. 	return 0;	
  178. }
  179.  
  180.  
  181.  
  182.  
  183. void solve() {
  184.  
  185. 	int k;
  186. 	cin >> k >> a;
  187. 	int n = a.size();
  188.  
  189. 	cout << consistency1(n, k) << " " << consistency2(n,k) <<  " " << consistency3(n,k) << endl;
  190.  
  191. 	// cout << consistency1(n, k) << " -> " << practice(n, k) << endl;
  192.  
  193. }
  194.  
  195.  
  196.  
  197.  
  198.  
  199. int32_t main() {
  200.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  201.  
  202.     int t = 1;
  203.     cin >> t;
  204.     while (t--) {
  205.         solve();
  206.     }
  207.  
  208.     return 0;
  209. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3
2 abc
2 aba
1 aa
stdout
copy 
2 2 2
3 3 3
3 3 3
https://ideone.com/isDcUJ
language:
C++14 (gcc 8.3)
created:
1 hour 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!