Niloy007

Maintain_The_Ratio_IIUC_Programming_Contest_2020

Apr 9th, 2021
437
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #define Niloy
  4. #define int int64_t
  5. #define MAX (int) 1e5 + 123
  6. #define MOD 1e9
  7. #define pb push_back
  8. #define pairs pair<int, int>
  9. #define vi vector<int>
  10. #define vb vector<bool>
  11. #define vii vector<pairs>
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define endl '\n'
  15. #define llu unsigned long long
  16. using namespace std;
  17. using namespace __gnu_pbds;
  18. // Policy Based Data Structure
  19. typedef tree< int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
  20. /* ----------------------------------------------------------------------------------- */
  21.  
  22. // Input/Output
  23. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  24. #define all(x) x.begin(), x.end()
  25. #define square(a) (a * a)
  26. #define mem(a, b) memset(a, b, sizeof(a))
  27.  
  28. // Fractional Number
  29. #define fraction()        cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
  30.  
  31. #define scan(a)           scanf("%lld", &a);
  32. #define scan2(a, b)       scanf("%lld %lld", &a, &b);
  33. #define scan3(a, b, c)    scanf("%lld %lld %lld", &a, &b, &c);
  34. #define scan4(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
  35.  
  36. #define scanD(a)          scanf("%lf", &a);
  37. #define scanD2(a, b)      scanf("%lf %lf", &a, &b);
  38. #define scanD3(a, b, c)   scanf("%lf %lf %lf", &a, &b, &c);
  39. #define scanD4(a, b, c, d)scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
  40.  
  41.  
  42. #define print(a)           printf("%lld\n", a);
  43. #define print2(a, b)       printf("%lld %lld\n", a, b);
  44. #define print3(a, b, c)    printf("%lld %lld %lld\n", a, b, c);
  45. #define print4(a, b, c, d) printf("%lld %lld %lld %lld\n", a, b, c, d);
  46.  
  47. #define printD(a)          printf("%lf\n", a);
  48. #define printD2(a, b)      printf("%lf %lf\n", a, b);
  49. #define printD3(a, b, c)   printf("%lf %lf %lf\n", a, b, c);
  50. #define printD4(a, b, c, d)printf("%lf %lf %lf %lf\n", a, b, c, d);
  51. #define printTwoD(a)       printf("%.2lf\n", a);
  52.  
  53. // File I/O
  54. #define read(x)  freopen(x, "r", stdin);
  55. #define write(x) freopen(x, "w", stdout);
  56.  
  57. // Loops
  58. #define rep(i, a, n) for (int i = a; i < n; i++)
  59. #define REP(i, a, n) for (int i = a; i <= n; i++)
  60. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
  61. #define REV(i, n, a) for (int i = n; i >= a; i--)
  62. #define inputArray(a,n) rep(i, 0, n) cin >> a[i];
  63. #define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
  64. #define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;
  65.  
  66. /* ----------------------------------------------------------------------------------- */
  67.  
  68. #define Cases  cout << "Case " << ++Case << ": ";
  69. #define __test int tt; int Case=0; cin >> tt; while(tt--)
  70. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
  71.  
  72. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
  73. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
  74. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
  75.  
  76. /* ----------------------------------------------------------------------------------- */
  77.  
  78. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
  79. int lcm(int n, int m) { return n / gcd(n, m) * m; }
  80.  
  81. struct debugger {
  82.     typedef string::iterator si;
  83.     static void call(si it, si ed) {}
  84.     template<typename T, typename ... aT>
  85.     static void call(si it, si ed, T a, aT... rest) {
  86.         string b;
  87.         for(; *it!=','; ++it)
  88.             if(*it!=' ')
  89.                 b+=*it;
  90.         cout << b << "=" << a << " ";
  91.         call(++it, ed, rest...);
  92.     }
  93. };
  94.  
  95. /* ----------------------------------------------------------------------------------- */
  96.  
  97. /// change ll to any data type
  98. /// less_equal for multiset increasing order
  99. /// less for set increasing order
  100. /// greater_equal for multiset decreasing order
  101. /// greater for set decreasing order
  102.  
  103. /// cout<<*X.find_by_order(1)<<endl; // iterator to the k-th largest element
  104. /// cout<<X.order_of_key(-5)<<endl;  // number of items in a set that are strictly smaller than our item
  105.  
  106. /* ----------------------------------------------------------------------------------- */
  107. void input() {
  108. #ifdef Niloy
  109.     read("input.txt");  
  110.     write("output.txt");
  111. #endif
  112. }
  113.  
  114. /* ----------------------------------------------------------------------------------- */
  115.  
  116. int sum0[MAX], sum1[MAX];
  117.  
  118. void solve() {
  119.     string s;
  120.     int k, n;
  121.     cin >> s >> k;
  122.     n = s.size();
  123.     rep(i, 0, n) {
  124.         sum0[i + 1] = (s[i] == '0') + sum0[i];
  125.         sum1[i + 1] = (s[i] == '1') + sum1[i];
  126.     }
  127.  
  128.     ordered_set ps;
  129.     map<int, int> cnt;
  130.     ps.insert(0);
  131.     cnt[0]++;
  132.     int ans = 0;
  133.  
  134.     REP(i, 1, n) {
  135.         int d1 = sum0[i] - (k * sum1[i]);
  136.         ans += ps.order_of_key(d1) + cnt[d1];
  137.         ps.insert(d1);
  138.         cnt[d1]++;
  139.     }
  140.     cout << ans << endl;
  141. }
  142.  
  143. int32_t main() {
  144.     // input();
  145.     // fastInput;
  146.     // solve();
  147.  
  148.     __test {
  149.         Cases;
  150.         solve();
  151.     }
  152.  
  153.     // showTime;
  154.     return 0;
  155. }
  156.  
  157.  
  158.  
RAW Paste Data