fork download
copy 
  1. /**
  2.  video: https://w...content-available-to-author-only...e.com/watch?v=VBerLS1JG4E
  3.  contest: https://c...content-available-to-author-only...s.com/group/FxFJrQUeaZ/contest/527641
  4.  problem: https://c...content-available-to-author-only...s.com/group/FxFJrQUeaZ/contest/527641/problem/F
  5.  rank: https://c...content-available-to-author-only...s.com/group/FxFJrQUeaZ/contest/527641/standings/groupmates/true
  6.  profile(me): https://c...content-available-to-author-only...s.com/profile/ThanhSteve2k11 (k1ngch0m-imissmath-nguyenquangthanh)
  7.  date/school/country: (SUN/06/OCT/2024-ChuVanAnSecondarySchool-DANANG-VIETNAM)
  8. **/
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. #define int long long
  12. #define double long double
  13. #define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
  14. #define endl "\n"
  15. #define sz(s) (int)s.size()
  16. #define gl(s) string s;getline(cin,s)
  17. #define cin(n) int n;cin >> n
  18. #define __lcm(a,b) a/__gcd(a,b)*b
  19. #define fset(x) fixed << setprecision(x)
  20. #define MOD (int)1e9+7
  21. #define maxn (int)1e5+1
  22. void FREOPEN(){freopen(".inp","r",stdin);freopen(".out","w",stdout);}
  23. int cnt[255+1], pref[255+1][maxn];
  24. bool ok(int l,int r,int k) {
  25.     // kt doan l->r co ok ko
  26.     // tinh nhanh so luong tung chu cai & kt chung co vuot qua k ko
  27.     for(int i='a';i<='z';i++) {
  28.         // dem so luong kitu i trong doan l->r
  29.         int cnt = pref[i][r] - pref[i][l-1];
  30.         if (cnt>k) return false;
  31.     }
  32.     return true;
  33. }
  34. void k1ngch0m() {
  35.     string s; cin >> s;
  36.     int SZ = sz(s);
  37.     s = '1'+s;// dich vi tri xau s ve 1
  38.     cin(k);
  39.     for(int i='a';i<='z';i++) {
  40.         // mang cong don cho kitu i
  41.         // pref[i][j] dung cho kitu da tinh so luong kitu i tu 1->j
  42.         for(int j=1;j<=SZ;j++) {
  43.             int x;
  44.             if (s[j]==i) x=1;
  45.             else x=0;
  46.             pref[i][j] = pref[i][j-1]+x;
  47.         }
  48.     }
  49.     // dem so cap i j sao cho tu i->j ko co kitu nao xuat hien qua k lan
  50.     int ans=0;
  51.     for(int i=1;i<=SZ;i++) {
  52.         int l=i, r=SZ, mid, pos=i-1;
  53.         while(l<=r) {
  54.             mid = (l+r)/2;
  55.             // kt doan tu i->mid co ok ko
  56.             if (ok(i,mid,k)) pos=mid, l=mid+1;
  57.             else r = mid-1;
  58.         }
  59.         ans+=pos-i+1;
  60.     }
  61.     cout << ans << endl;
  62.     // C2: binary_search + prefix_sum
  63. }
  64. signed main() {
  65.     /**FREOPEN();**/ FAST;
  66.     int test=1; cin >> test;
  67.     while (test--) k1ngch0m();
  68. }
  69.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1
abc
1
stdout
copy 
6
https://ideone.com/uaGOsi
ACPbasicB-CD5:binary_search-5F
language:
C++14 (clang 8.0)
created:
47 days ago
visibility:
secret

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!