Submission #677713

#	Time	Username	Problem	Language	Result	Execution time	Memory
677713		finn__	Palinilap (COI16_palinilap)	C++17	0 / 100	140 ms	53404 KiB

palinilap

#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;
    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 = i;
        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;

        if (i)
        {
            size_t a = 0, b = 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;

            if (i < n - 1 && a < i && i + 1 < n - 1)
            {
                size_t oa = a;
                a++;
                b = 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;
                events.push_back({i - oa, 0, 1});
                events.push_back({i, oa, 0});
                revevents.push_back({i + oa - 1, 0, 1});
                revevents.push_back({i - 1, oa, 0});
            }
        }

        if (i && i < n - 1 && a < i && i + a < n - 1)
        {
            size_t oa = a;
            a++;
            b = 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), 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;
            events.push_back({i - oa, 0, 1});
            events.push_back({i, oa, 0});
            revevents.push_back({i + oa, 0, 1});
            revevents.push_back({i, oa, 0});
        }
    }

    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 (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:148:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |             if (i != s[it->i] - 'a')
      |                 ~~^~~~~~~~~~~~~~~~~
palinilap.cpp:171:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |             if (i != s[it->i] - 'a')
      |                 ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46