2015年2月8日 星期日

Codechef February Challenge 2015 Chef and Strange Formula

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

char P[2000000]; int Pn;
int Q;

int pre[2000000][4];
ll cnt[2000000][4][4];

int ch(char c)
{
    if( c == 'c' ) return 0;
    else if( c == 'h' ) return 1;
    else if( c == 'e' ) return 2;
    else return 3;
}

int main()
{
    scanf("%s", P+1);
    Pn = strlen(P+1);

    for(int Pi = 1; Pi <= Pn; Pi++)
    {
        for(int i = 0; i < 4; i++)
            pre[Pi][i] = pre[Pi-1][i];

        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                cnt[Pi][i][j] = cnt[Pi-1][i][j];

        int now = ch(P[Pi]);

        pre[Pi][now]++;

        for(int i = 0; i < 4; i++)
            cnt[Pi][i][now] += pre[Pi][i];
    }

    scanf("%d", &Q);

    for(int Qi = 0; Qi < Q; Qi++)
    {
        char a, b; int L, R;
        scanf(" %c %c %d %d", &a, &b, &L, &R);

        int p = ch(a), q = ch(b);

        ll Ans = cnt[R][p][q]-cnt[L-1][p][q];
        Ans -= (ll)pre[L-1][p]*(pre[R][q]-pre[L-1][q]);

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

沒有留言:

張貼留言