2015年3月16日 星期一

Codechef March Challenge 2015 Count Substrings

// http://www.codechef.com/problems/STRSUB/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

int T;
int N, K, Q;

char c[200000];
int ter[200000];
int cnt[2];

ll pre[200000];

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d %d %d", &N, &K, &Q);

        scanf("%s", c+1);

        int st = 1, ed = 1;

        cnt[0] = cnt[1] = 0;

        while( st <= N )
        {
            while( ed <= N )
            {
                if( cnt[0]+(c[ed]=='0') > K ) break;
                if( cnt[1]+(c[ed]=='1') > K ) break;

                cnt[c[ed]-'0']++;
                ed++;
            }

            ter[st] = ed;
            pre[st] = pre[st-1]+ed-st;

            cnt[c[st]-'0']--;
            st++;
        }

        for(int Qi = 0; Qi < Q; Qi++)
        {
            ll Ans = 0;

            int L, R;
            scanf("%d %d", &L, &R);
            R++;

            int l = L-1, r = R;

            while( l+1 != r )
            {
                int mid = (l+r)/2;

                if( ter[mid] > R ) r = mid;
                else l = mid;
            }

            Ans += pre[l]-pre[L-1];
            Ans += (ll)(R-r+1)*(R-r)/2;

            printf("%lld\n", Ans);
        }


    }
}

沒有留言:

張貼留言