oj.uz

Submission #403841

# Submission time Handle Problem Language Result Execution time Memory
403841 2021-05-13T13:58:45 Z opukittpceno_hhr Palindromes (APIO14_palindrome) C++17
100 / 100
 827 ms 53560 KB 
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;
const int ALP = 26;

namespace Hash {
    const int MOD = 1e9 + 7;
    const int BASE = 31;

    int add(int a, int b) {
        if (a + b < MOD) {
            return a + b;
        }
        return a + b - MOD;
    }

    int sub(int a, int b) {
        if (a >= b) {
            return a - b;
        }
        return a - b + MOD;
    }

    int mul(int a, int b) {
        return 1LL * a * b % MOD;
    }

    int n;

    int pw[N];
    int h[N];
    int rh[N];

    int req(int i, int j, int len) {
        i = n - 1 - i;
        int F = sub(rh[i + len], mul(rh[i], pw[len]));
        int S = sub(h[j + len], mul(h[j], pw[len]));
        return F == S;
    }

    void init(string s) {
        n = (int)s.size();
        pw[0] = 1;
        for (int i = 0; i < n; i++) {
            pw[i + 1] = mul(pw[i], BASE);
        }
        for (int i = 0; i < n; i++) {
            h[i + 1] = add(s[i], mul(h[i], BASE));
        }
        reverse(s.begin(), s.end());
        for (int i = 0; i < n; i++) {
            rh[i + 1] = add(s[i], mul(rh[i], BASE));
        }
        reverse(s.begin(), s.end());
    }
}

namespace SparceTable {
    const int L = 20;

    int pw[N];
    int mn[L][N];

    void init(int n, int *a) {
        for (int i = 0; i < n; i++) {
            mn[0][i] = a[i];
        }
        for (int i = 0; i + 1 < L; i++) {
            for (int j = 0; j + 2 * (1 << i) <= n; j++) {
                mn[i + 1][j] = min(mn[i][j], mn[i][j + (1 << i)]);
            }
        }
        pw[1] = 0;
        for (int i = 2; i <= n; i++) {
            pw[i] = pw[i / 2] + 1;
        }
    }

    int get(int l, int r) {
        int p = pw[r - l];
        return min(mn[p][l], mn[p][r - (1 << p)]);
    }
}

namespace SuffixArray {
    int n;

    string s;

    int sa[N];
    int wr[N];

    int cur_class[N];
    tuple<int, int, int> tos[N];
    tuple<int, int, int> mtos[N];
    tuple<int, int, int> ntos[N];
    int pcnt[N];
    int scnt[N];

    void do_sort() {
        for (int i = 0; i < n; i++) {
            pcnt[i] = 0;
            scnt[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            pcnt[get<0>(tos[i])]++;
            scnt[get<1>(tos[i])]++;
        }
        for (int i = 1; i < n; i++) {
            pcnt[i] += pcnt[i - 1];
            scnt[i] += scnt[i - 1];
        }
        for (int i = 0; i < n; i++) {
            pcnt[i]--;
            scnt[i]--;
        }
        for (int i = 0; i < n; i++) {
            mtos[scnt[get<1>(tos[i])]] = tos[i];
            scnt[get<1>(tos[i])]--;
        }
        for (int i = n - 1; i >= 0; i--) {
            ntos[pcnt[get<0>(mtos[i])]] = mtos[i];
            pcnt[get<0>(mtos[i])]--;
        }
        for (int i = 0; i < n; i++) {
            tos[i] = ntos[i];
        }
    }

    void build_sa() {
        s.push_back(0);
        n++;
        {
            vector<char> hv;
            for (auto c : s) {
                hv.push_back(c);
            }
            sort(hv.begin(), hv.end());
            hv.resize(unique(hv.begin(), hv.end()) - hv.begin());
            for (int i = 0; i < n; i++) {
                cur_class[i] = lower_bound(hv.begin(), hv.end(), s[i]) - hv.begin();
            }
        }
        for (int l = 1; l < n; l *= 2) {
            for (int i = 0; i < n; i++) {
                tos[i] = make_tuple(cur_class[i], cur_class[(i + l) % n], i);
            }
            do_sort();
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cur_class[get<2>(tos[i])] = cnt;
                if (i + 1 < n) {
                    cnt += (get<0>(tos[i]) != get<0>(tos[i + 1]) || get<1>(tos[i]) != get<1>(tos[i + 1]));
                }
            }
        }
        n--;
        for (int i = 0; i < n; i++) {
            wr[i] = cur_class[i] - 1;
        }
        for (int i = 0; i < n; i++) {
            sa[wr[i]] = i;
        }
    }

    int l[N];

    void build_lcp() {
        for (int i = 0; i < n; i++) {
            int k = 0;
            if (i > 0) {
                k = l[wr[i - 1]];
            }
            k--;
            k = max(k, 0);
            int in_l = wr[i];
            if (in_l + 1 == n) {
                l[in_l] = -1;
            } else {
                int j = sa[in_l + 1];
                while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
                    k++;
                }
                l[in_l] = k;
            }
        }
        SparceTable::init(n, l);
    }

    int lcp(int i, int j) {
        if (i == j) {
            return n - i;
        }
        i = wr[i];
        j = wr[j];
        if (i > j) swap(i, j);
        return SparceTable::get(i, j);
    }

    void init(string s_) {
        s = s_;
        n = (int)s.size();
        build_sa();
        build_lcp();
    }
}

void solve(vector<int> v, int ml, int add, ll &ans) {
    int n = (int)v.size();
    vector<int> l(n);
    vector<int> r(n);
    {
        vector<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && v[st.back()] >= v[i]) {
                st.pop_back();
            }
            if (st.empty()) {
                l[i] = -1;
            } else {
                l[i] = st.back();
            }
            st.push_back(i);
        }
    }
    {
        vector<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && v[st.back()] >= v[i]) {
                st.pop_back();
            }
            if (st.empty()) {
                r[i] = n;
            } else {
                r[i] = st.back();
            }
            st.push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        ans = max(ans, (ll)(r[i] - l[i]) * (v[i] * ml + add));
    }
}

int cnt[ALP];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    Hash::init(s);
    SuffixArray::init(s);
    ll ans = 0;

    auto cmp = [&](pair<int, int> X, pair<int, int> Y) {
        int i1, len1, i2, len2;
        tie(i1, len1) = X;
        tie(i2, len2) = Y;
        int sk = SuffixArray::lcp(i1, i2);
        if (sk >= len1 || sk >= len2) {
            return len1 < len2;
        }
        i1 += sk;
        i2 += sk;
        return (i1 == n || s[i1] < s[i2]);
    };

    //single
    {
        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
            ans = max(ans, (ll)cnt[s[i] - 'a']);
        }
    }

    //even
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            int l = -1;
            int r = n +1;
            while (r  - l > 1) {
                int mid = (r + l) / 2;
                if (mid <= i && mid + i <= n && Hash::req(i - 1, i, mid)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            mx = l;
            ans = max(ans, (ll)2 * mx);
            if (mx != -1) {
                ip.push_back({i, mx});
            }
        }
        sort(ip.begin(), ip.end(), cmp);
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second, ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        solve(val, 2, 0, ans);
    }
    //odd
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            int l = -1;
            int r = n +1;
            while (r  - l > 1) {
                int mid = (r + l) / 2;
                if (mid <= i && mid + i + 1 <= n && Hash::req(i - 1, i + 1, mid)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            mx = l;
            ans = max(ans, (ll)2 * mx + 1);
            if (mx != -1) {
                ip.push_back({i, mx + 1});
            }
        }
        sort(ip.begin(), ip.end(), cmp);
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second,  ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        solve(val, 2, -1, ans);
    }
    cout << ans << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 532 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1996 KB Output is correct
2 Correct 13 ms 1996 KB Output is correct
3 Correct 16 ms 2064 KB Output is correct
4 Correct 15 ms 2048 KB Output is correct
5 Correct 13 ms 1996 KB Output is correct
6 Correct 13 ms 2000 KB Output is correct
7 Correct 12 ms 1996 KB Output is correct
8 Correct 15 ms 1980 KB Output is correct
9 Correct 14 ms 1996 KB Output is correct
10 Correct 13 ms 1980 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 17304 KB Output is correct
2 Correct 133 ms 17080 KB Output is correct
3 Correct 177 ms 17344 KB Output is correct
4 Correct 168 ms 17108 KB Output is correct
5 Correct 168 ms 16964 KB Output is correct
6 Correct 161 ms 16964 KB Output is correct
7 Correct 158 ms 16964 KB Output is correct
8 Correct 208 ms 17172 KB Output is correct
9 Correct 194 ms 17000 KB Output is correct
10 Correct 174 ms 16940 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 52704 KB Output is correct
2 Correct 488 ms 52472 KB Output is correct
3 Correct 585 ms 53560 KB Output is correct
4 Correct 547 ms 52580 KB Output is correct
5 Correct 673 ms 52488 KB Output is correct
6 Correct 536 ms 52592 KB Output is correct
7 Correct 538 ms 52612 KB Output is correct
8 Correct 827 ms 52684 KB Output is correct
9 Correct 823 ms 52568 KB Output is correct
10 Correct 639 ms 52620 KB Output is correct
11 Correct 473 ms 52708 KB Output is correct
12 Correct 808 ms 52776 KB Output is correct