Ideone.com

fork download

#include <bits/stdc++.h>
 
#define pb push_back
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
 
using namespace std;
 
typedef long long vlong;
 
#define MANALEN 200000
 
/*
1. First assign string to manacher, arr[]
2. Call init
3. Call Preprocess to convert string
4. Call calc to calculate array p[]
*/
 
char arr[MANALEN+10], brr[MANALEN+10];
int p[MANALEN+10];
int cum[26][MANALEN+10];
int fr[26][MANALEN+10];
 
struct MANACHER {
    int an, bn, mxpalin, mxcenter;
 
    void init() {
        //Assign string to arr
        an = strlen ( arr );
        CLR(cum,0);
        CLR(fr,0);
    }
 
    //aba -> ^#a#b#a#$
    void preprocess() { ///Converts string
        int cur = 0;
        brr[cur++] = '^';
        FOR(i,0,an-1) {
            brr[cur++] = '#';
            brr[cur++] = arr[i];
        }
        brr[cur++] = '#';
        brr[cur++] = '$';
        brr[cur] = 0;
        bn = cur;
    }
 
    void calc() { ///Calculates Manacher Array
        int c = 0, r = 0;
        FOR(i,1,bn-2) {
            int mi = c - (i-c);
 
            p[i] = (r > i )? MIN ( r - i, p[mi] ): 0;
 
            while ( brr[i+p[i]+1] == brr[i-p[i]-1] ) {
                p[i]++;
            }
 
            if ( i + p[i] > r ) {
                r = i + p[i];
                c = i;
            }
        }
 
        mxpalin = 0; mxcenter = 0;
        FOR(i,1,bn-2) {
            if ( p[i] > mxpalin ) {
                mxpalin = p[i];
                mxcenter = i;
            }
        }
 
    }
 
    ///Build cumulative array for each letter
    ///cum[0][x] gives me number of 'a' from 0 to x.
    void extra() {
        FOR(c,0,25){
            cum[c][0] = 0;
            FOR(joker,1,bn-1){
                int cur = 0;
                if ( brr[joker] >= 'a' && brr[joker] <= 'z' ) {
                    if ( brr[joker] - 'a' == c ) cur = 1;
                }
                cum[c][joker] = cum[c][joker-1] + cur;
            }
        }
    }
 
    ///Calculate for each center, how many "c" it has in it.
    ///If it has x, then mark[x]++; Meaning, I have a center which has x number of c.
    void moreExtra() {
        FOR(c,0,25){
            FOR(joker,1,bn-2) {
                int palin = p[joker];
                ///Now find how many palindrome exist in the palindrome with center joker
                int st = joker - p[joker]; ///RTE not possible. st >= 1
                int en = joker + p[joker]; ///en <= bn-2
 
                ///st-1 >= 0, cause brr[0] is not part of any palindrome with center >= 1.
 
                if ( st - 1 < 0 ) while(1);
 
                int freq = cum[c][en] - cum[c][st-1];
                //debug ( joker, brr[joker], st, en, freq, c );
                fr[c][freq]++;
            }
        }
 
        ///Calculate cumulate such that fr[c][x] has sum of fr[c][x] + fr[c][x+2] + fr[c][x+4] ...
        FOR(c,0,25){
            fr[c][bn-1] = 0;
            fr[c][bn] = 0;
            ROF(joker,0,bn-2) {
                fr[c][joker] += fr[c][joker+2];
            }
        }
    }
 
}mana;
 
 
char buf[100000+10];
 
int main () {
    int kase, cnt = 0;
    scanf ( "%d", &kase );
 
    while ( kase-- ) {
        int n;
        scanf ( "%d", &n );
        scanf ( "%s", arr );
 
        mana.init();
        mana.preprocess();
        mana.calc();
 
        mana.extra();
        mana.moreExtra();
 
        int q;
        scanf ( "%d", &q );
        scanf ( "%s", buf );
 
        printf ( "Case %d:\n", ++cnt );
        FOR(iron,0,q-1) {
            int x;
            scanf ( "%d", &x );
 
            int c = buf[iron] - 'a';
 
            if ( x <= 0 || x > n ) {
                printf ( "0\n" );
                continue;
            }
 
            int res = 0;
            res = fr[c][x];
 
            printf ( "%d\n", res );
        }
    }
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIEZPUihpLHgseSkgZm9yKHZsb25nIGkgPSAoeCkgOyBpIDw9ICh5KSA7ICsraSkKI2RlZmluZSBST0YoaSx4LHkpIGZvcih2bG9uZyBpID0gKHkpIDsgaSA+PSAoeCkgOyAtLWkpCiNkZWZpbmUgQ0xSKHgseSkgbWVtc2V0KHgseSxzaXplb2YoeCkpCiNkZWZpbmUgTUlOKGEsYikgKChhKTwoYik/KGEpOihiKSkKI2RlZmluZSBNQVgoYSxiKSAoKGEpPihiKT8oYSk6KGIpKQojZGVmaW5lIEFMTCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSBMQ00oeCx5KSAoKCh4KS9nY2QoKHgpLCh5KSkpKih5KSkKI2RlZmluZSBTWih4KSAoKHZsb25nKSh4KS5zaXplKCkpCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgdmxvbmc7CgojZGVmaW5lIE1BTkFMRU4gMjAwMDAwCgovKgoxLiBGaXJzdCBhc3NpZ24gc3RyaW5nIHRvIG1hbmFjaGVyLCBhcnJbXQoyLiBDYWxsIGluaXQKMy4gQ2FsbCBQcmVwcm9jZXNzIHRvIGNvbnZlcnQgc3RyaW5nCjQuIENhbGwgY2FsYyB0byBjYWxjdWxhdGUgYXJyYXkgcFtdCiovCgpjaGFyIGFycltNQU5BTEVOKzEwXSwgYnJyW01BTkFMRU4rMTBdOwppbnQgcFtNQU5BTEVOKzEwXTsKaW50IGN1bVsyNl1bTUFOQUxFTisxMF07CmludCBmclsyNl1bTUFOQUxFTisxMF07CgpzdHJ1Y3QgTUFOQUNIRVIgewogICAgaW50IGFuLCBibiwgbXhwYWxpbiwgbXhjZW50ZXI7CgogICAgdm9pZCBpbml0KCkgewogICAgICAgIC8vQXNzaWduIHN0cmluZyB0byBhcnIKICAgICAgICBhbiA9IHN0cmxlbiAoIGFyciApOwogICAgICAgIENMUihjdW0sMCk7CiAgICAgICAgQ0xSKGZyLDApOwogICAgfQoKICAgIC8vYWJhIC0+IF4jYSNiI2EjJAogICAgdm9pZCBwcmVwcm9jZXNzKCkgeyAvLy9Db252ZXJ0cyBzdHJpbmcKICAgICAgICBpbnQgY3VyID0gMDsKICAgICAgICBicnJbY3VyKytdID0gJ14nOwogICAgICAgIEZPUihpLDAsYW4tMSkgewogICAgICAgICAgICBicnJbY3VyKytdID0gJyMnOwogICAgICAgICAgICBicnJbY3VyKytdID0gYXJyW2ldOwogICAgICAgIH0KICAgICAgICBicnJbY3VyKytdID0gJyMnOwogICAgICAgIGJycltjdXIrK10gPSAnJCc7CiAgICAgICAgYnJyW2N1cl0gPSAwOwogICAgICAgIGJuID0gY3VyOwogICAgfQoKICAgIHZvaWQgY2FsYygpIHsgLy8vQ2FsY3VsYXRlcyBNYW5hY2hlciBBcnJheQogICAgICAgIGludCBjID0gMCwgciA9IDA7CiAgICAgICAgRk9SKGksMSxibi0yKSB7CiAgICAgICAgICAgIGludCBtaSA9IGMgLSAoaS1jKTsKCiAgICAgICAgICAgIHBbaV0gPSAociA+IGkgKT8gTUlOICggciAtIGksIHBbbWldICk6IDA7CgogICAgICAgICAgICB3aGlsZSAoIGJycltpK3BbaV0rMV0gPT0gYnJyW2ktcFtpXS0xXSApIHsKICAgICAgICAgICAgICAgIHBbaV0rKzsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKCBpICsgcFtpXSA+IHIgKSB7CiAgICAgICAgICAgICAgICByID0gaSArIHBbaV07CiAgICAgICAgICAgICAgICBjID0gaTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgbXhwYWxpbiA9IDA7IG14Y2VudGVyID0gMDsKICAgICAgICBGT1IoaSwxLGJuLTIpIHsKICAgICAgICAgICAgaWYgKCBwW2ldID4gbXhwYWxpbiApIHsKICAgICAgICAgICAgICAgIG14cGFsaW4gPSBwW2ldOwogICAgICAgICAgICAgICAgbXhjZW50ZXIgPSBpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgIH0KCiAgICAvLy9CdWlsZCBjdW11bGF0aXZlIGFycmF5IGZvciBlYWNoIGxldHRlcgogICAgLy8vY3VtWzBdW3hdIGdpdmVzIG1lIG51bWJlciBvZiAnYScgZnJvbSAwIHRvIHguCiAgICB2b2lkIGV4dHJhKCkgewogICAgICAgIEZPUihjLDAsMjUpewogICAgICAgICAgICBjdW1bY11bMF0gPSAwOwogICAgICAgICAgICBGT1Ioam9rZXIsMSxibi0xKXsKICAgICAgICAgICAgICAgIGludCBjdXIgPSAwOwogICAgICAgICAgICAgICAgaWYgKCBicnJbam9rZXJdID49ICdhJyAmJiBicnJbam9rZXJdIDw9ICd6JyApIHsKICAgICAgICAgICAgICAgICAgICBpZiAoIGJycltqb2tlcl0gLSAnYScgPT0gYyApIGN1ciA9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBjdW1bY11bam9rZXJdID0gY3VtW2NdW2pva2VyLTFdICsgY3VyOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vL0NhbGN1bGF0ZSBmb3IgZWFjaCBjZW50ZXIsIGhvdyBtYW55ICJjIiBpdCBoYXMgaW4gaXQuCiAgICAvLy9JZiBpdCBoYXMgeCwgdGhlbiBtYXJrW3hdKys7IE1lYW5pbmcsIEkgaGF2ZSBhIGNlbnRlciB3aGljaCBoYXMgeCBudW1iZXIgb2YgYy4KICAgIHZvaWQgbW9yZUV4dHJhKCkgewogICAgICAgIEZPUihjLDAsMjUpewogICAgICAgICAgICBGT1Ioam9rZXIsMSxibi0yKSB7CiAgICAgICAgICAgICAgICBpbnQgcGFsaW4gPSBwW2pva2VyXTsKICAgICAgICAgICAgICAgIC8vL05vdyBmaW5kIGhvdyBtYW55IHBhbGluZHJvbWUgZXhpc3QgaW4gdGhlIHBhbGluZHJvbWUgd2l0aCBjZW50ZXIgam9rZXIKICAgICAgICAgICAgICAgIGludCBzdCA9IGpva2VyIC0gcFtqb2tlcl07IC8vL1JURSBub3QgcG9zc2libGUuIHN0ID49IDEKICAgICAgICAgICAgICAgIGludCBlbiA9IGpva2VyICsgcFtqb2tlcl07IC8vL2VuIDw9IGJuLTIKCiAgICAgICAgICAgICAgICAvLy9zdC0xID49IDAsIGNhdXNlIGJyclswXSBpcyBub3QgcGFydCBvZiBhbnkgcGFsaW5kcm9tZSB3aXRoIGNlbnRlciA+PSAxLgoKICAgICAgICAgICAgICAgIGlmICggc3QgLSAxIDwgMCApIHdoaWxlKDEpOwoKICAgICAgICAgICAgICAgIGludCBmcmVxID0gY3VtW2NdW2VuXSAtIGN1bVtjXVtzdC0xXTsKICAgICAgICAgICAgICAgIC8vZGVidWcgKCBqb2tlciwgYnJyW2pva2VyXSwgc3QsIGVuLCBmcmVxLCBjICk7CiAgICAgICAgICAgICAgICBmcltjXVtmcmVxXSsrOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAvLy9DYWxjdWxhdGUgY3VtdWxhdGUgc3VjaCB0aGF0IGZyW2NdW3hdIGhhcyBzdW0gb2YgZnJbY11beF0gKyBmcltjXVt4KzJdICsgZnJbY11beCs0XSAuLi4KICAgICAgICBGT1IoYywwLDI1KXsKICAgICAgICAgICAgZnJbY11bYm4tMV0gPSAwOwogICAgICAgICAgICBmcltjXVtibl0gPSAwOwogICAgICAgICAgICBST0Yoam9rZXIsMCxibi0yKSB7CiAgICAgICAgICAgICAgICBmcltjXVtqb2tlcl0gKz0gZnJbY11bam9rZXIrMl07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cgp9bWFuYTsKCgpjaGFyIGJ1ZlsxMDAwMDArMTBdOwoKaW50IG1haW4gKCkgewogICAgaW50IGthc2UsIGNudCA9IDA7CiAgICBzY2FuZiAoICIlZCIsICZrYXNlICk7CgogICAgd2hpbGUgKCBrYXNlLS0gKSB7CiAgICAgICAgaW50IG47CiAgICAgICAgc2NhbmYgKCAiJWQiLCAmbiApOwogICAgICAgIHNjYW5mICggIiVzIiwgYXJyICk7CgogICAgICAgIG1hbmEuaW5pdCgpOwogICAgICAgIG1hbmEucHJlcHJvY2VzcygpOwogICAgICAgIG1hbmEuY2FsYygpOwoKICAgICAgICBtYW5hLmV4dHJhKCk7CiAgICAgICAgbWFuYS5tb3JlRXh0cmEoKTsKCiAgICAgICAgaW50IHE7CiAgICAgICAgc2NhbmYgKCAiJWQiLCAmcSApOwogICAgICAgIHNjYW5mICggIiVzIiwgYnVmICk7CgogICAgICAgIHByaW50ZiAoICJDYXNlICVkOlxuIiwgKytjbnQgKTsKICAgICAgICBGT1IoaXJvbiwwLHEtMSkgewogICAgICAgICAgICBpbnQgeDsKICAgICAgICAgICAgc2NhbmYgKCAiJWQiLCAmeCApOwoKICAgICAgICAgICAgaW50IGMgPSBidWZbaXJvbl0gLSAnYSc7CgogICAgICAgICAgICBpZiAoIHggPD0gMCB8fCB4ID4gbiApIHsKICAgICAgICAgICAgICAgIHByaW50ZiAoICIwXG4iICk7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaW50IHJlcyA9IDA7CiAgICAgICAgICAgIHJlcyA9IGZyW2NdW3hdOwoKICAgICAgICAgICAgcHJpbnRmICggIiVkXG4iLCByZXMgKTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K

Runtime error #stdin #stdout 0.05s 45312KB

stdin

Standard input is empty

stdout

https://ideone.com/brZKXL

Blog UVa 12833 - Daily Potato

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language