Submission #1019940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019940		andrei_iorgulescu	Palindromes (APIO14_palindrome)	C++14	100 / 100	990 ms	124516 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
char a[300005];

vector<int> modulo = {(int)1e9 + 123, (int)1e9 + 321, (int)998244353};
vector<int> base = {31, 59, 43};
int powbase[3][300005],invpowbase[3][300005];
int h[3][300005],revh[3][300005];///sum din a[i] * B^(i - 1)

int lgpow(int x,int y, int M)
{
    int z = 1;
    while (y != 0)
    {
        if (y % 2 == 1)
            z = z * x % M;
        x = x * x % M;
        y /= 2;
    }
    return z;
}

vector<double> ev[300005];///cu + daca il bag, - daca il scot

bool pal(int l,int r)
{
    if (l < 1 or r > n or l > r)
        return false;
    for (int ch = 0; ch < 3; ch++)
    {
        int h1 = (h[ch][r] - h[ch][l - 1] + modulo[ch]) % modulo[ch] * invpowbase[ch][l - 1] % modulo[ch];
        int h2 = (revh[ch][l] - revh[ch][r + 1] + modulo[ch]) % modulo[ch] * invpowbase[ch][n - r] % modulo[ch];
        if (h1 != h2)
            return false;
    }
    return true;
}

vector<int> get_hash(int l, int r)
{
    vector<int> rsp;
    for (int ch = 0; ch < 3; ch++)
    {
        int h1 = (h[ch][r] - h[ch][l - 1] + modulo[ch]) % modulo[ch] * invpowbase[ch][l - 1] % modulo[ch];
        rsp.push_back(h1);
    }
    return rsp;
}

int lft[300005];
map<vector<int>,int> id;
pair<int,int> what[300005];///sa stiu si eu cam cum arata un string de acel id
int cnt_id;
int f[300005];
int l2[300005];

signed main()
{
    string when_what_where_how_why;
    cin >> when_what_where_how_why;
    n = when_what_where_how_why.size();
    for (int i = 1; i <= n; i++)
        a[i] = when_what_where_how_why[i - 1];
    for (int ch = 0; ch < 3; ch++)
    {
        powbase[ch][0] = invpowbase[ch][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            powbase[ch][i] = base[ch] * powbase[ch][i - 1] % modulo[ch];
            if (i >= 2)
                invpowbase[ch][i] = invpowbase[ch][1] * invpowbase[ch][i - 1] % modulo[ch];
            else
                invpowbase[ch][i] = lgpow(base[ch],modulo[ch] - 2,modulo[ch]);
        }
        for (int i = 1; i <= n; i++)
            h[ch][i] = (h[ch][i - 1] + (a[i] - 'a' + 1) * powbase[ch][i - 1]) % modulo[ch];
        for (int i = n; i >= 1; i--)
            revh[ch][i] = (revh[ch][i + 1] + (a[i] - 'a' + 1) * powbase[ch][n - i]) % modulo[ch];
    }
    for (int i = 1; i <= n; i++)
    {
        int st = 0,pas = 1 << 18;
        while (pas != 0)
        {
            if (pal(i - st - pas,i + st + pas))
                st += pas;
            pas /= 2;
        }
        ev[i].push_back(i);
        ev[i + st + 1].push_back(-i);
    }
    for (int i = 1; i < n; i++)
    {
        int st = 0,pas = 1 << 18;
        while (pas != 0)
        {
            if (pal(i - st - pas + 1,i + st + pas))
                st += pas;
            pas /= 2;
        }
        if (st == 0)
            continue;
        double lol = (double)i + 0.5d;
        ev[i + 1].push_back(lol);
        ev[i + st + 1].push_back(-lol);
    }
    multiset<double> ms;
    for (int i = 1; i <= n; i++)
    {
        for (auto it : ev[i])
        {
            double vl = it;
            if (vl > 0)
                ms.insert(vl);
            else
                ms.erase(ms.find(-vl));
        }
        double hmm = *ms.begin();
        double d = (double)i - hmm;
        d *= (2.0d);
        lft[i] = i - d;
        if (ms.size() == 1)
            continue;
        ms.erase(ms.find(hmm));
        double hmm2 = *ms.begin();
        d = (double)i - hmm2;
        d *= (2.0d);
        l2[i] = i - d;
        ms.insert(hmm);
    }
    for (int i = 1; i <= n; i++)
    {
        vector<int>cur = get_hash(lft[i],i);
        int vr = id[cur];
        if (vr == 0)
            id[cur] = ++cnt_id,vr = cnt_id;
        what[vr] = {lft[i],i};
        f[vr]++;
    }
    vector<pair<int,int>> ord;
    for (int i = 1; i <= cnt_id; i++)
        ord.push_back({what[i].second - what[i].first + 1,i});
    sort(ord.begin(),ord.end());
    reverse(ord.begin(),ord.end());
    int ans = 0;
    for (auto it : ord)
    {
        ans = max(ans,it.first * f[it.second]);
        if (it.first == 1)
            continue;
        int cn = what[it.second].second;
        vector<int> h2 = get_hash(l2[cn],cn);
        int id2 = id[h2];
        f[id2] += f[it.second];
    }
    cout << ans;
    return 0;
}

/**
Maxim N palindroame distincte etc
Voi vrea pentru fiecare sa retin frecventa lui
Pentru asta, merg cu i de la 1 la N, iau cel mai mare palindrom care se termina pe i
Ii gasesc id-ul (ori un id nou ori ceva id vechi fiindca deja exista)
Acum, vreau sa adaug 1 pe toate palindroamele care se termina pe i <=> toate sufixele palindrom ale lui pal[id] <=> toate prefixele palindrom
Dau f[id]++

La final, vreau sa propag f-urile pe toate prefixele palindrom
Foarte simplu, iau palindroamele descrescator dupa lungime, pentru asta o sa am f[id] updatat si il consider la raspuns
Fie pal[id'] = prefixul maxim palindrom al lui pal[id] (daca pal[id] are lungime 1, ma opresc)
Dau f[id'] += f[id] and we move on
**/

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27