oj.uz

Submission #249169

# Submission time Handle Problem Language Result Execution time Memory
249169 2020-07-14T12:56:39 Z receed Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 2944 KB 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 600001, M = 1 << 19;
string s;
int mp[N], mx[N], ord[N], c[N], cnt[N], a[N], n, pc[N], pord[N], lcp[N], pos[N], tr[M * 2];

int getl(int p, int m, int v=1, int l=0, int r=M) {
    if (tr[v] >= m || p <= l)
        return -1;
    if (r - l == 1)
        return l;
    int x = getl(p, m, v * 2 + 1, (l + r) / 2, r);
    if (x != -1)
        return x;
    return getl(p, m, v * 2, l, (l + r) / 2);
}

int getr(int p, int m, int v=1, int l=0, int r=M) {
    if (tr[v] >= m || r <= p)
        return n;
    if (r - l == 1)
        return l;
    int x = getr(p, m, v * 2, l, (l + r) / 2);
    if (x != n)
        return x;
    return getr(p, m, v * 2 + 1, (l + r) / 2, r);
}

int sm(int x, int y) {
    return x + y >= n ? x + y - n : x + y;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s;
    n = s.size();
    int l = 0, r = 0;
    rep(i, 2 * n - 1) {
        if (i <= 2 * r)
            mp[i] = min(mp[(l + r) * 2 - i], r * 2 - i + 1);
        if (i % 2 == 0)
            mp[i] = max(mp[i], 1);
        while (i - mp[i] - 1 >= 0 && (i + mp[i] + 1) / 2 < n && s[(i - mp[i] - 1) / 2] == s[(i + mp[i] + 1) / 2])
            mp[i] += 2;
        if ((i + mp[i] - 1) / 2 > r) {
            l = (i + mp[i] + 1) / 2;
            r = (i + mp[i] - 1) / 2;
        }
    }
    int ps = 2 * n - 1;
    for (int i = n - 1; i >= 0; i--) {
        while (mp[ps] < ps - i * 2 + 1)
            ps--;        
        mx[i] = ps - i * 2 + 1;
    }
    // rep(i, 2 * n - 1)
    //     cout << mp[i] << '\n';
    // rep(i, n)
    //     cout << mx[i] << '\n';
    n++;
    rep(i, n) {
        a[i] = (i == n - 1 ? 0 : s[i] - 'a' + 1);
        cnt[a[i] + 1]++;
    }
    rep(i, 27)
        cnt[i + 1] += cnt[i];
    rep(i, n)
        ord[cnt[a[i]]++] = i;
    int cc = 1;
    rep(i, n - 1) {
        c[ord[i + 1]] = c[ord[i]];
        if (s[ord[i]] != s[ord[i + 1]]) {
            c[ord[i + 1]]++;
            cc++;
        }
    }
    for (int l = 1; l < n; l *= 2) {
        rep(i, cc + 1)
            cnt[i] = 0;
        rep(i, n) {
            cnt[c[i] + 1]++;
            pord[i] = ord[i];
            pc[i] = c[i];
        }
        rep(i, cc)
            cnt[i + 1] += cnt[i];
        rep(i, n) {
            int q = pord[i] - l;
            if (q < 0)
                q += n;
            ord[cnt[c[q]]++] = q;
        }
        c[ord[0]] = 0;
        rep(i, n - 1) {
            c[ord[i + 1]] = c[ord[i]];
            if (pc[ord[i]] != pc[ord[i + 1]] || pc[sm(ord[i], l)] != pc[sm(ord[i + 1], l)])
                c[ord[i + 1]]++;
        }
        cc = c[ord[n - 1]] + 1;
    }
    rep(i, n)
        pos[ord[i]] = i;
    cc = 0;
    rep(i, n) {
        cc = max(cc - 1, 0);
        // cc = 0;
        if (pos[i] == n - 1)
            cc = 0;
        else
            while (s[i + cc] == s[ord[pos[i] + 1] + cc])
                cc++;
        lcp[pos[i]] = cc;
    }
    // rep(i, n - 1)
    //     assert(s.substr(ord[i], lcp[i]) == s.substr(ord[i + 1], lcp[i]));
    // rep(i, n)
    //     cout << lcp[pos[i]] << '\n';
    rep(i, n) {
        // cout << ord[i] << '\n';
        // cout << s.substr(ord[i]) << '\n';
    }
    rep(i, n - 1)
        tr[M + i] = lcp[i];
    for (int i = M - 1; i > 0; i--)
        tr[i] = min(tr[i * 2], tr[i * 2 + 1]);
    ll ans = 0;
    rep(i, n) {
        ll cl = getl(pos[i], mx[i]), cr = getr(pos[i], mx[i]);
        ans = max(ans, (cr - cl) * mx[i]);
    }
    cout << ans;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2936 KB Output is correct
2 Correct 32 ms 2936 KB Output is correct
3 Correct 93 ms 2936 KB Output is correct
4 Correct 70 ms 2940 KB Output is correct
5 Correct 9 ms 2944 KB Output is correct
6 Correct 10 ms 2944 KB Output is correct
7 Correct 17 ms 2944 KB Output is correct
8 Correct 8 ms 2944 KB Output is correct
9 Correct 8 ms 2944 KB Output is correct
10 Correct 9 ms 2944 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 1144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 1148 KB Time limit exceeded
2 Halted 0 ms 0 KB -