Submission #677729

# Submission time Handle Problem Language Result Execution time Memory
677729 2023-01-04T08:53:02 Z finn__ Palinilap (COI16_palinilap) C++17
54 / 100
153 ms 42120 KB
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000009
#define BASE 10016

struct poly_hash
{
    vector<uint64_t> p, h;

    poly_hash(string const &s)
    {
        h = vector<uint64_t>(s.size());
        p = vector<uint64_t>(s.size());
        h[0] = s[0];
        p[0] = 1;

        for (size_t i = 1; i < s.size(); i++)
        {
            h[i] = ((h[i - 1] * BASE) + s[i]) % MOD;
            p[i] = (p[i - 1] * BASE) % MOD;
        }
    }

    uint64_t range_hash(size_t i, size_t j)
    {
        if (!i)
            return h[j - 1];
        return (h[j - 1] - (p[j - i] * h[i - 1]) % MOD + MOD) % MOD;
    }
};

struct event
{
    size_t i, val, i0;
    bool start;

    bool operator<(event const &y) const
    {
        return i < y.i;
    }
};

int main()
{
    string s;
    cin >> s;
    size_t const n = s.size();

    poly_hash h(s);
    reverse(s.begin(), s.end());
    poly_hash revh(s);
    reverse(s.begin(), s.end());

    size_t max_palindromes = 0;
    vector<vector<int>> delta(n, vector<int>(26, 0));
    vector<event> events, revevents;

    for (size_t i = 0; i < n; i++)
    {
        size_t a = 0, b = min(i, n - i - 1);
        while (a < b)
        {
            size_t mid = (a + b + 1) / 2;
            if (h.range_hash(i - mid, i + 1) == revh.range_hash(n - 1 - (i + mid), n - i))
                a = mid;
            else
                b = mid - 1;
        }

        max_palindromes += a + 1;

        events.push_back({i - a, a, i - a, 1});
        events.push_back({i, a, i - a, 0});
        revevents.push_back({i + a, a, i + a, 1});
        revevents.push_back({i, a, i + a, 0});

        if (i)
        {
            size_t a = 0, b = min(i, n - i);
            while (a < b)
            {
                size_t mid = (a + b + 1) / 2;
                if (h.range_hash(i - mid, i) == revh.range_hash(n - 1 - (i + mid - 1), n - i))
                    a = mid;
                else
                    b = mid - 1;
            }
            max_palindromes += a;

            events.push_back({i - a, a, i - a, 1});
            events.push_back({i, a, i - a, 0});
            revevents.push_back({i + a - 1, a, i + a - a, 1});
            revevents.push_back({i - 1, a, i + a - 1, 0});

            if (a < i && i + a < n)
            {
                size_t oa = a;
                a++;
                b = min(i, n - i);
                while (a < b)
                {
                    size_t mid = (a + b + 1) / 2;
                    if (h.range_hash(i - mid, i - oa - 1) == revh.range_hash(n - 1 - (i + mid - 1), n - 1 - (i + oa)))
                        a = mid;
                    else
                        b = mid - 1;
                }
                delta[i - oa - 1][s[i + oa] - 'a'] += a - oa;
                delta[i + oa][s[i - oa - 1] - 'a'] += a - oa;
            }
        }

        if (i && i < n - 1 && a < i && i + a < n - 1)
        {
            size_t oa = a;
            a++;
            b = min(i, n - i - 1);
            while (a < b)
            {
                size_t mid = (a + b + 1) / 2;
                if (h.range_hash(i - mid, i - oa - 1) == revh.range_hash(n - 1 - (i + mid), n - 1 - (i + oa + 1)))
                    a = mid;
                else
                    b = mid - 1;
            }
            delta[i - oa - 1][s[i + oa + 1] - 'a'] += a - oa;
            delta[i + oa + 1][s[i - oa - 1] - 'a'] += a - oa;
        }
    }

    sort(events.begin(), events.end());
    sort(revevents.begin(), revevents.end());

    size_t v = 0, c = 0;
    for (auto it = events.begin(); it != events.end(); it++)
    {
        for (auto jt = it; jt != events.end() && jt->i == it->i; jt++)
            if (jt->start)
            {
                c++;
            }
            else
            {
                c--;
                v -= jt->val;
            }
        v += c;
        for (size_t i = 0; i < 26; i++)
            if (i != s[it->i] - 'a')
                delta[it->i][i] -= v;

        while (it != events.end() - 1 && (it + 1)->i == it->i)
            it++;
    }

    v = 0, c = 0;

    for (auto it = revevents.rbegin(); it != revevents.rend(); it++)
    {
        for (auto jt = it; jt != revevents.rend() && jt->i == it->i; jt++)
            if (jt->start)
            {
                c++;
            }
            else
            {
                c--;
                v -= jt->val;
            }
        v += c;
        for (size_t i = 0; i < 26; i++)
            if (i != s[it->i] - 'a')
                delta[it->i][i] -= v;

        while (it != revevents.rend() - 1 && (it + 1)->i == it->i)
            it++;
    }

    int max_del = 0;
    for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < 26; j++)
            max_del = max(max_del, delta[i][j]);

    cout << max_palindromes + max_del << '\n';
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:150:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if (i != s[it->i] - 'a')
      |                 ~~^~~~~~~~~~~~~~~~~
palinilap.cpp:173:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  173 |             if (i != s[it->i] - 'a')
      |                 ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 2888 KB Output is correct
2 Correct 7 ms 2888 KB Output is correct
3 Correct 10 ms 2888 KB Output is correct
4 Correct 4 ms 1744 KB Output is correct
5 Correct 7 ms 2760 KB Output is correct
6 Correct 7 ms 2888 KB Output is correct
7 Correct 7 ms 2888 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 153 ms 42016 KB Output is correct
2 Incorrect 126 ms 42120 KB Output isn't correct
3 Halted 0 ms 0 KB -