Submission #1396561

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int N, phi[100009], ap[100009][26];
long long L, R, S[1009], P[1009], ans[30];
char a[400009], sir[200009];

void add (int st, int dr, long long coef)
{
    for (int i=0; i<26; i++)
        ans[i] += 1LL * coef * (ap[dr][i] - ap[st - 1][i]);
}
vector < pair < pair < long long, long long >, long long > > Q[109];

void solve (int lev, long long st, long long dr, long long coef)
{
    if (lev == 0)
    {
        add (st, dr, coef);
        return ;
    }
    if (dr <= S[lev - 1])
    {
        solve (lev - 1, st, dr, coef);
        return ;
    }
    if (st > S[lev - 1])
    {
        solve (lev - 1, st - S[lev - 1], dr - S[lev - 1], coef);
        return ;
    }
    solve (lev - 1, st, S[lev - 1], coef);
    solve (lev - 1, 1, dr - S[lev - 1], coef);
}

void prop (int lev)
{
    for (auto it : Q[lev])
    {
        long long st = it.first.first, dr = it.first.second, coef = it.second;
        if (dr <= S[lev - 1]) Q[lev - 1].push_back ({{st, dr}, coef});
        else
        if (st > S[lev - 1]) Q[lev - 1].push_back ({{st - S[lev - 1], dr - S[lev - 1]}, coef});
        else
        {
            Q[lev - 1].push_back ({{st, S[lev - 1]}, coef});
            Q[lev - 1].push_back ({{1, dr - S[lev - 1]}, coef});
        }
    }
}

void unify (int lev)
{
    vector < pair < long long, long long > > norm;
    for (auto it : Q[lev])
        norm.push_back ({it.first.first, +it.second}), norm.push_back ({it.first.second + 1, -it.second});
/*    printf ("before: ");
    for (auto it : Q[lev])
        printf ("{[%lld, %lld] %lld} ", it.first.first, it.first.second, it.second);
    printf ("\n");*/

    Q[lev].clear ();
    sort (norm.begin (), norm.end ());
    long long lst = -1, curr = 0;
    for (int i=0; i<norm.size (); i++)
    {
        int j;
        for (j=i; j<norm.size (); j++)
            if (norm[j].first != norm[i].first) break;
        j --;
        for (int k=i; k<=j; k++)
            curr += norm[k].second;
        if (curr != 0 && j + 1 < norm.size ())
            Q[lev].push_back ({{norm[i].first, norm[j + 1].first - 1}, curr});
        i = j;
    }
/*    printf ("after: ");
    for (auto it : Q[lev])
        printf ("{[%lld, %lld] %lld} ", it.first.first, it.first.second, it.second);
    printf ("\n");*/
}

void prnt (int lev)
{
    printf ("now: ");
    for (auto it : Q[lev])
        printf ("{[%lld, %lld] %lld} ", it.first.first, it.first.second, it.second);
    printf ("\n");
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%s\n", sir + 1), N = strlen (sir + 1) / 2;
scanf ("%lld %lld", &L, &R);
for (int i=1; i<=N; i++)
{
    for (int j=0; j<26; j++)
        ap[i][j] = ap[i - 1][j];
    a[i] = sir[i], ap[i][a[i] - 'a'] ++;
}
int k = 0;
for (int i=2; i<=N; i++)
{
    while (k && sir[i] != sir[k + 1]) k = phi[i];
    k += (sir[i] == sir[k + 1]);
    phi[i] = k;
}
S[0] = N, P[0] = phi[N];
int steps = 0;
while (S[steps] <= R)
{
    steps ++;
//    for (int i=oldS + 1; i<=2 * oldS - P; i++)
  //      a[i] = a[i - oldS];
    S[steps] = 2LL * S[steps - 1] - P[steps - 1], P[steps] = S[steps - 1] - P[steps - 1];;
}
//solve (steps, L, R, 1);
Q[steps].push_back ({{L, R}, 1});
for (int i=steps; i>0; i--)
    prop (i), unify (i - 1);
for (auto it : Q[0])
    add (it.first.first, it.first.second, it.second);
for (int i=0; i<26; i++)
    printf ("%lld%c", ans[i], " \n"[i == 25]);
return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:97:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%s\n", sir + 1), N = strlen (sir + 1) / 2;
                                                  ^
./Main.cpp:98:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%lld %lld", &L, &R);
                            ^

Judge Result