oj.uz

Submission #1019940

# Submission time Handle Problem Language Result Execution time Memory
1019940 2024-07-11T10:56:30 Z andrei_iorgulescu Palindromes (APIO14_palindrome) C++14
100 / 100
 990 ms 124516 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 27144 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 4 ms 27112 KB Output is correct
11 Correct 3 ms 26972 KB Output is correct
12 Correct 3 ms 27224 KB Output is correct
13 Correct 3 ms 26972 KB Output is correct
14 Correct 3 ms 26972 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 3 ms 26972 KB Output is correct
19 Correct 5 ms 27148 KB Output is correct
20 Correct 4 ms 26968 KB Output is correct
21 Correct 4 ms 26972 KB Output is correct
22 Correct 4 ms 26972 KB Output is correct
23 Correct 3 ms 26972 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 4 ms 26972 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 26972 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26972 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 5 ms 27484 KB Output is correct
4 Correct 6 ms 27228 KB Output is correct
5 Correct 4 ms 27224 KB Output is correct
6 Correct 5 ms 27484 KB Output is correct
7 Correct 4 ms 27228 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27228 KB Output is correct
10 Correct 4 ms 27228 KB Output is correct
11 Correct 4 ms 27224 KB Output is correct
12 Correct 4 ms 27224 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29788 KB Output is correct
2 Correct 17 ms 29532 KB Output is correct
3 Correct 22 ms 30160 KB Output is correct
4 Correct 20 ms 30288 KB Output is correct
5 Correct 15 ms 29532 KB Output is correct
6 Correct 16 ms 29756 KB Output is correct
7 Correct 17 ms 29532 KB Output is correct
8 Correct 8 ms 28036 KB Output is correct
9 Correct 8 ms 27908 KB Output is correct
10 Correct 14 ms 29020 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 57288 KB Output is correct
2 Correct 186 ms 56136 KB Output is correct
3 Correct 217 ms 62132 KB Output is correct
4 Correct 231 ms 59456 KB Output is correct
5 Correct 151 ms 55364 KB Output is correct
6 Correct 150 ms 51908 KB Output is correct
7 Correct 183 ms 54344 KB Output is correct
8 Correct 64 ms 40276 KB Output is correct
9 Correct 102 ms 45388 KB Output is correct
10 Correct 161 ms 53452 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 107444 KB Output is correct
2 Correct 780 ms 102752 KB Output is correct
3 Correct 950 ms 124516 KB Output is correct
4 Correct 990 ms 114012 KB Output is correct
5 Correct 583 ms 101704 KB Output is correct
6 Correct 737 ms 100188 KB Output is correct
7 Correct 735 ms 93792 KB Output is correct
8 Correct 207 ms 54508 KB Output is correct
9 Correct 208 ms 54308 KB Output is correct
10 Correct 680 ms 92128 KB Output is correct
11 Correct 686 ms 102664 KB Output is correct
12 Correct 272 ms 60396 KB Output is correct