Submission #1356484

#TimeUsernameProblemLanguageResultExecution timeMemory
1356484xorshiftPalindromes (APIO14_palindrome)C++20
0 / 100
0 ms348 KiB
#include <bits/stdc++.h>
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pill = pair<int, ll>;
using vpill = vector<pill>;
using plli = pair<ll, int>;
using vplli = vector<plli>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; cin >> s;
    int n = s.size();

    vint count(26);
    for (char c: s) count[c - 'a']++;

    int counter = 0;
    map<pint, int> mapper;
    for (int i = 0; i < 26; i++) mapper[{i, -1}] = counter++;
    map<int, pint> occsz;
    for (int i = 0; i < 26; i++) occsz[mapper[{i, -1}]] = {count[i], 1};
    
    set<pint> pstart;
    pstart.insert({0, mapper[{s[0], -1}]});

    for (int i = 1; i < n; i++) {
        int c = s[i] - 'a';
        int lv = s[i-1] - 'a';
        pint insval;
        if (c != lv) insval = {i, mapper[{i, -1}]};
        else {
            auto it = pstart.end()--;
            pint nv = {c, it->second};
            if (!mapper.count(nv)) mapper[nv] = counter++;
            insval = {it->first, mapper[nv]};
        }
        for (auto it = pstart.begin(); it != pstart.end(); it = pstart.erase(it)) {
            if (it->first == 0) continue;
            int lst = s[it->first-1] - 'a';
            if (lst == c) {
                pint nv = {c, it->second};
                if (!mapper.count(nv)) mapper[nv] = counter++;
                int mnv = mapper[nv], mst = it->second;
                occsz[mnv] = {occsz[mnv].first+1, occsz[mst].second+2};
                pint nstart = {it->first-1, mnv};
                if (nstart.first != 0) pstart.insert(nstart);
            }
        }
        pstart.insert(insval);
    }
    int res = 0;
    for (auto& [key, val]: occsz) res = max(res, val.first*val.second);

    cout << res << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...