By deadline_savvy, history, 6 weeks ago,

I have been trying to solve this Count Substrings. But I am getting WA in the result. 2 subtask gets AC but not all. Read the editorial but not able to code it properly. Maybe I haven't understood the approach completely. Can anyone explain to me where I am wrong??

My code:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define inf (1LL<<60)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
using namespace std;
void solve()
{
ll n,k,q;
string s;
cin>>n>>k>>q;
cin>>s;
vector<ll> far(n);
vector<ll> sumfar(n);
ll c0=0,c1=0;
ll j=0;
if(s[0]=='1') c1++;
else c0++;

//precomputing far[i] : last index till which string is valid
for(ll i=0;i<n;++i){
while(j<n && c0<=k && c1<=k){
j+=1;
if(j==n) break;
if(s[j]=='1') c1++;
else c0++;
}
far[i]=j;
if(s[i] == '1') c1=c1-1;
else c0 = c0-1;
}

//precomputing sumfar[i]: valid strings till index i
sumfar[0]=far[0];
for(ll i=1;i<n;++i){
sumfar[i] = sumfar[i-1] + far[i];
}

//calculating valid strings
ll ans=0;
ll sp,ep,L,R;
for(ll i=1;i<=q;++i){
cin>>sp>>ep;
L = sp-1;
R = ep-1;
ll d = upper_bound(far.begin()+L,far.begin()+ep,R)-far.begin();
if(d == ep){
ans = (R-L+1)*(R+1) - ((R+L)*(R-L+1))/2;
}
else{
d = d-1;
ans = sumfar[d] + (R-d)*(R+1) - ((R+L)*(R-L+1))/2;
if(!L==0){
ans =  ans - sumfar[L-1];
}
}
cout<<ans<<endl;
}

int main()
{
fast_io;
ll t;
cin>>t;
for(int i=1;i<=t;++i){
solve();
}
return 0;
}


========================================

• 0