Advertisement
momo2345

maintain the ratio

Sep 24th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace __gnu_pbds;
  6. typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
  7. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define endl "\n"
  9. #define mn int main()
  10. #define frac() cout.unsetf(ios::floatfield);cout.precision(6);cout.setf(ios::fixed,ios::floatfield);
  11. const int mx=1e6+123;
  12. int s0[mx],s1[mx];
  13. mn
  14. {
  15.     suni;
  16.     int t; cin>>t;
  17.     for(int j=1;j<=t;j++)
  18.     {
  19.         string s; cin>>s;
  20.         ll k;cin>>k;
  21.         ll n=s.size();
  22.         for(int i=0;i<n;i++){
  23.             s0[i+1]=(s[i]=='0')+s0[i];
  24.             s1[i+1]=(s[i]=='1')+s1[i];
  25.         }
  26.     ordered_set p;
  27.     map<ll,ll>cnt;
  28.     ll ans=0;
  29.     p.insert(0);
  30.     cnt[0]++;
  31.     for(int i=1;i<=n;i++){
  32.         ll d= s0[i]-(k*s1[i]);
  33.         ans+=p.order_of_key(d)+cnt[d];
  34.         p.insert(d);
  35.         cnt[d]++;
  36.     }
  37.       cout<<"Case "<<j<<": "<<ans<<endl;
  38.  
  39.     }
  40. }
  41.  
  42.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement