Submission #916357

#	Time	Username	Problem	Language	Result	Execution time	Memory
916357		Alcabel	Palindromes (APIO14_palindrome)	C++17	53 / 100	805 ms	15344 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7, p = 31, maxn = 3e5 + 1;

struct Modint {
    int x;
    Modint() { x = 0; }
    Modint(int _x) {
        while (_x >= mod) { _x -= mod; }
        while (_x < 0) { _x += mod; }
        x = _x;
    }
    Modint(long long _x) {
        if (_x >= mod || _x <= -mod) { _x %= mod; }
        if (_x < 0) { _x += mod; }
        x = _x;
    }
    Modint operator+(const Modint& other) const {
        return Modint(x + other.x);
    }
    Modint operator-(const Modint& other) const {
        return Modint(x - other.x);
    }
    Modint operator*(const Modint& other) const {
        return Modint(x * 1ll * other.x);
    }
    void operator+=(const Modint& other) {
        *this = *this + other;
    }
    void operator-=(const Modint& other) {
        *this = *this - other;
    }
    void operator*=(const Modint& other) {
        *this = *this * other;
    }
    ~Modint() {}
};

Modint pExp[maxn];

struct DSU {
    int n, maxcompsz;
    vector<int> par, sz;
    DSU() {}
    DSU(int _n) {
        n = _n, maxcompsz = 0;
        par.resize(n);
        sz.resize(n);
        clear();
    }
    void clear() {
        maxcompsz = 0;
        for (int i = 0; i < n; ++i) {
            par[i] = -1, sz[i] = 0;
        }
    }
    void create(int i) {
        par[i] = i, sz[i] = 1;
        maxcompsz = max(maxcompsz, 1);
    }
    int getParent(int v) {
        if (par[v] != v) {
            par[v] = getParent(par[v]);
        }
        return par[v];
    }
    void uniteSets(int v, int u) {
        v = getParent(v), u = getParent(u);
        if (v == u) {
            return;
        }
        sz[v] += sz[u];
        par[u] = v;
        maxcompsz = max(maxcompsz, sz[v]);
    }
    ~DSU() {}
};

int pos[maxn];

void countSort(vector<int>& a, vector<int>& tmp, const vector<int>& c) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        pos[i] = 0;
    }
    for (const int& x : c) {
        ++pos[x];
    }
    for (int i = n - 1, pref = n; i >= 0; --i) {
        pref -= pos[i];
        pos[i] = pref;
    }
    for (const int& x : a) {
        tmp[pos[c[x]]++] = x;
    }
    swap(a, tmp);
}

void buildSufArr(const string& s, vector<int>& sufArr, vector<int>& c) {
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        sufArr[i] = i;
    }
    sort(sufArr.begin(), sufArr.end(), [&](const int& A, const int& B) {
        return s[A] < s[B];
    });
    c[sufArr[0]] = 0;
    for (int i = 1; i < n; ++i) {
        c[sufArr[i]] = c[sufArr[i - 1]];
        if (s[sufArr[i - 1]] != s[sufArr[i]]) {
           ++c[sufArr[i]];
        }
    }
    vector<int> tmp(n);
    for (int k = 0; (1 << k) < n; ++k) {
        for (int i = 0; i < n; ++i) {
            sufArr[i] -= (1 << k);
            if (sufArr[i] < 0) {
                sufArr[i] += n;
            }
        }
        countSort(sufArr, tmp, c);
        tmp[sufArr[0]] = 0;
        for (int i = 1; i < n; ++i) {
            tmp[sufArr[i]] = tmp[sufArr[i - 1]];
            int nxtprev = sufArr[i - 1] + (1 << k);
            if (nxtprev >= n) { nxtprev -= n; }
            int nxtcur = sufArr[i] + (1 << k);
            if (nxtcur >= n) { nxtcur -= n; }
            if (c[sufArr[i - 1]] != c[sufArr[i]] || c[nxtprev] != c[nxtcur]) {
                ++tmp[sufArr[i]];
            }
        }
        swap(c, tmp);
    }
}

vector<Modint> h, revH;
string s;

bool equalOne(int l1, int r1, int l2, int r2) {
    int val1 = ((h[r1 + 1] - h[l1]) * pExp[(int)h.size() - 2 - r1]).x;
    int val2 = ((h[r2 + 1] - h[l2]) * pExp[(int)h.size() - 2 - r2]).x;
    return val1 == val2;
}

int getLcp(int i, int j) {
    int left = 0, right = (int)s.size() - max(i, j); 
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (equalOne(i, i + mid - 1, j, j + mid - 1)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left;
}

/*void buildLcp(const string& s, vector<int>& sufArr, vector<int>& c, vector<int>& lcp) {
    lcp[0] = 0;
    for (int i = 1; i < (int)s.size() - 1; ++i) {
        int ptr = sufArr[i], j = sufArr[i + 1];
        int left = 0, right = (int)s.size() - max(ptr, j);
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (equalOne(ptr, ptr + mid - 1, j, j + mid - 1)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        lcp[i] = left;
    }
}*/

bool equal(int l1, int r1, int l2, int r2) {
    int val1 = ((h[r1 + 1] - h[l1]) * pExp[(int)h.size() - 2 - r1]).x;
    int val2 = ((revH[l2] - revH[r2 + 1]) * pExp[l2]).x;
    return val1 == val2;
}

//sparse Table

void solve() {
    cin >> s;
    int n = s.size();
    h.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        h[i + 1] = h[i] + pExp[i] * (s[i] - 'a' + 1);
    }
    revH.resize(n + 1);
    for (int i = n - 1; i >= 0; --i) {
        revH[i] = revH[i + 1] + pExp[n - 1 - i] * (s[i] - 'a' + 1);
        // cerr << "i: " << i << ", revH: " << revH[i].x << '\n';
    }
    vector<int> odd(n), even(n);
    // even
    for (int i = 0; i < n; ++i) {
        int left = 0, right = min(i, n - i) + 1;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (equal(i - mid, i - 1, i, i + mid - 1)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        even[i] = left;
        // cerr << "i: " << i << ", even: " << even[i] << '\n';
    }
    // odd
    for (int i = 0; i < n; ++i) {
        int left = 0, right = min(i + 1, n - i) + 1;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (equal(i - mid + 1, i, i, i + mid - 1)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        odd[i] = left;
        // cerr << "i: " << i << ", odd: " << odd[i] << '\n';
    }
    s += '#';
    ++n;
    vector<int> sufArr(n), c(n);
    buildSufArr(s, sufArr, c);
    /*for (int i = 0; i < n; ++i) {
        cerr << sufArr[i] << ' ';
    }
    cerr << '\n';
    for (int i = 0; i < n; ++i) {
        cerr << c[i] << ' ';
    }
    cerr << '\n';*/
    vector<pair<int, int>> evs(n - 1);
    long long ans = 0;
    DSU dsu(n);
    set<int> alive;
    // even lengths
    for (int i = 0; i < n - 1; ++i) {
        evs[i] = {2 * even[i], i};
    }
    sort(evs.rbegin(), evs.rend());
    for (int len = n / 2 * 2, ptr = 0; len > 0; len -= 2) {
        while (ptr < (int)evs.size() && evs[ptr].first == len) {
            int i = evs[ptr].second;
            // cerr << "i: " << i << '\n';
            // cerr << "c: " << c[i] << '\n';
            dsu.create(i);
            auto it = alive.emplace(c[i]).first;
            if (it != alive.begin()) {
                auto prv = prev(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*prv] << '\n';
                while (getLcp(sufArr[*prv], i) * 2 >= len) {
                    // cerr << "merge: " << *prv << '\n';
                    dsu.uniteSets(i, sufArr[*prv]);
                    prv = alive.erase(prv);
                    if (prv == alive.begin()) {
                        break;
                    } else {
                        prv = prev(prv);
                    }
                }
            }
            if (*it != *alive.rbegin()) {
                auto nxt = next(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*nxt] << '\n';
                while (getLcp(sufArr[*nxt], i) * 2 >= len) {
                    dsu.uniteSets(i, sufArr[*nxt]);
                    nxt = alive.erase(nxt);
                    if (nxt == alive.end()) {
                        break;
                    }
                }
            }
            ++ptr;
        }
        // cerr << "len: " << len << ", sz: " << dsu.maxcompsz << '\n';
        ans = max(ans, dsu.maxcompsz * 1ll * len);
    }
    // odd lengths
    dsu.clear();
    alive.clear();
    for (int i = 0; i < n; ++i) {
        evs[i] = {2 * odd[i] - 1, i};
    }
    sort(evs.rbegin(), evs.rend());
    for (int len = (n % 2 == 0 ? n - 1 : n), ptr = 0; len > 0; len -= 2) {
        while (ptr < (int)evs.size() && evs[ptr].first == len) {
            int i = evs[ptr].second;
            dsu.create(i);
            auto it = alive.emplace(c[i]).first;
            if (it != alive.begin()) {
                auto prv = prev(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*prv] << '\n';
                while (getLcp(sufArr[*prv], i) * 2 - 1 >= len) {
                    // cerr << "merge: " << *prv << '\n';
                    dsu.uniteSets(i, sufArr[*prv]);
                    prv = alive.erase(prv);
                    if (prv == alive.begin()) {
                        break;
                    } else {
                        prv = prev(prv);
                    }
                }
            }
            if (*it != *alive.rbegin()) {
                auto nxt = next(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*nxt] << '\n';
                while (getLcp(sufArr[*nxt], i) * 2 - 1 >= len) {
                    dsu.uniteSets(i, sufArr[*nxt]);
                    nxt = alive.erase(nxt);
                    if (nxt == alive.end()) {
                        break;
                    }
                }
            }
            ++ptr;
        }
        // cerr << "len: " << len << ", sz: " << dsu.maxcompsz << '\n';
        ans = max(ans, dsu.maxcompsz * 1ll * len);
    }
    cout << ans << '\n';
    /*vector<int> lcp(n - 1);
    buildLcp(s, sufArr, c, lcp);*/
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    pExp[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        pExp[i] = pExp[i - 1] * p;
    }

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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