deadline_savvy's blog

By deadline_savvy, history, 6 weeks ago, In English

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;
}

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it