oj.uz

Submission #164886

# Submission time Handle Problem Language Result Execution time Memory
164886 2019-11-23T21:22:23 Z godwind Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 72300 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>

using namespace std;


#define less less228
#define left left228
#define right right228

template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}


random_device rnd;

template<typename T> void shuffle(vector< T > &v) {
    for (int i = 1; i < (int)v.size(); ++i) {
        swap(v[rnd() % i], v[i]);
    }
    for (int i = (int)v.size() - 1; i; --i) {
        swap(v[rnd() % i], v[i]);
    }
}

const int N = 300 * 1000 + 7;
const long long BASE = 141, MOD = 1e9 + 9;
const int INF = 1e9 + 228;

int cnt[N], pp[N], cc[N];

long long mod(long long x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

vector<int> get_suffmas(string s) {
    s += '$';
    int n = (int)s.size();
    vector<int> p(n), c(n);
    for (int i = 0; i < n; ++i) {
        ++cnt[(int)s[i]];
    }
    for (int i = 1; i < 256; ++i) {
        cnt[i] += cnt[i - 1];
    }
    for (int i = 0; i < n; ++i) {
        p[--cnt[(int)s[i]]] = i;
    }
    c[p[0]] = 0;
    for (int i = 1; i < n; ++i) {
        c[p[i]] = c[p[i - 1]];
        if (s[p[i]] != s[p[i - 1]]) ++c[p[i]];
    }
    int i1 = 0, i2 = 0;
    int h = 0;
    for (int d = 0; (1 << d) <= n; ++d) {
        h = (1 << d);
        memset(pp, 0, sizeof pp);
        memset(cc, 0, sizeof cc);
        memset(cnt, 0, sizeof cnt);
        for (int i = 0; i < n; ++i) {
            pp[i] = p[i] - h;
            if (pp[i] < 0) pp[i] += n;
            ++cnt[c[pp[i]]];
        }
        for (int i = 1; i < n; ++i) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = n - 1; i + 1; --i) {
            p[--cnt[c[pp[i]]]] = pp[i];
        }
        cc[p[0]] = 0;
        for (int i = 1; i < n; ++i) {
            cc[p[i]] = cc[p[i - 1]];
            i1 = p[i] + h;
            if (i1 >= n) i1 -= n;
            i2 = p[i - 1] + h;
            if (i2 >= n) i2 -= n;
            if (c[p[i]] != c[p[i - 1]] || c[i1] != c[i2]) {
                ++cc[p[i]];
            }
        }
        for (int i = 0; i < n; ++i) {
            c[i] = cc[i];
        }
    }
    vector<int> ans;
    for (int i : p) {
        if (i != n - 1) ans.push_back(i);
    }
    return ans;
}

vector<int> get_lcp(string s, vector<int> p) {
    int n = (int)s.size();
    vector<int> lcp(n - 1), pos(n);
    for (int i = 0; i < n; ++i) {
        pos[p[i]] = i;
    }
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (k) --k;
        if (pos[i] == n - 1) {
            k = 0;
        } else {
            int j = p[pos[i] + 1];
            while (max(i, j) + k < n && s[i + k] == s[j + k]) ++k;
            lcp[pos[i]] = k;
        }
    }
    return lcp;
}

string s;
int n;
long long h[N], hr[N], base[N];
int l_even[N], l_odd[N], st_even[N][20], st_odd[N][20], lg[N], len_odd[N], len_even[N];
long long answer;

long long gh(int l, int r) {
    return mod(h[r] - h[l - 1] * base[r - l + 1]);
}
long long gr(int l, int r) {
    return mod(hr[l] - hr[r + 1] * base[r - l + 1]);
}

void pre() {
    base[0] = 1;
    for (int i = 1; i <= n; ++i) {
        base[i] = mod(base[i - 1] * BASE);
    }
    for (int i = 1; i <= n; ++i) {
        h[i] = mod(h[i - 1] * BASE + (int)s[i - 1]);
    }
    for (int i = n; i; --i) {
        hr[i] = mod(hr[i + 1] * BASE + (int)s[i - 1]);
    }
    int l = 0, r = 0;
    for (int i = 1; i <= n; ++i) {
        int k = 0;
        if (i > r) {
            ;
        } else {
            k = min(r - i, len_odd[l + r - i]);
        }
        while (i + k <= n && i - k > 0 && s[i + k - 1] == s[i - k - 1]) ++k;
        if (i + k - 1 > r) {
            r = i + k - 1;
            l = i - k + 1;
        }
        len_odd[i] = k;
        l_odd[i] = i - k + 1;
        uax(answer, 2LL * k - 1);
    }
    l = r = 0;
    for (int i = 1; i <= n; ++i) {
        int k = 0;
        if (i > r) {
            ;
        } else {
            uax(k, min(r - i - 1, len_even[l + r - i - 1]));
        }
        while (i - k > 0 && i + k + 1 <= n && s[i + k] == s[i - k - 1]) ++k;
        if (i + k > r) {
            r = i + k;
            l = i - k + 1;
        }
        len_even[i] = k;
        l_even[i] = i - k + 1;
     
        uax(answer, 2LL * k);
    }
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i >> 1] + 1;
    }
    l_even[n] = INF;
    for (int i = 1; i <= n; ++i) {
        st_odd[i][0] = l_odd[i];
        st_even[i][0] = l_even[i];
    }
    for (int k = 1; k <= lg[n]; ++k) {
        for (int i = 1; i <= n - (1 << k); ++i) {
            st_odd[i][k] = min(st_odd[i][k - 1], st_odd[i + (1 << (k - 1))][k - 1]);
            st_even[i][k] = min(st_even[i][k - 1], st_even[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int k;

inline int get_odd(int l, int r) {
    k = lg[r - l + 1];
    return min(st_odd[l][k], st_odd[r - (1 << k) + 1][k]);
}
inline int get_even(int l, int r) {
    k = lg[r - l + 1];
    return min(st_even[l][k], st_even[r - (1 << k) + 1][k]);
}

int max_len = 0, stop = 0, low = 0, high = 0;

inline int findmax(int l, int r) {
    if (l == r) return 1;
    max_len = 1;
    stop = l + (r - l + 1 + 1) / 2 - 1;
    low = l;
    high = stop + 1;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        if (get_odd(mid, stop) <= l) low = mid;
        else high = mid;
    }
    if (get_odd(low, low) <= l) uax(max_len, (low - l + 1) * 2 - 1);

    stop = l + (r - l + 1) / 2 - 1;
    low = l;
    high = stop + 1;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        if (get_even(mid, stop) <= l) low = mid;
        else high = mid;
    }
    if (get_even(low, low) <= l) uax(max_len, (low - l + 1) * 2);
    return max_len;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    n = (int)s.size();
    pre();
    vector<int> p = get_suffmas(s);
    vector<int> lcp = get_lcp(s, p);
    vector<int> gol(n), gor(n);
    for (int i = 0; i < n - 1; ++i) {
        gol[i] = -1;
        gor[i] = n - 1;
    }
    vector<int> st;
    for (int i = 0; i < n - 1; ++i) {
        while (!st.empty() && lcp[st.back()] > lcp[i]) {
            gor[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    int pal = 0, cht = 0;
    for (int i = n - 2; i >= 0; --i) {
        while (!st.empty() && lcp[st.back()] > lcp[i]) {
            gol[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = 0; i < n - 1; ++i) {
        if (lcp[i] == 0) continue;
        pal = findmax(p[i] + 1, p[i] + lcp[i] - 1 + 1);
        cht = gor[i] - gol[i];
        uax(answer, (long long)pal * (long long)cht);
    }
    cout << answer << '\n';
    return 0;

}
// RU_023

/*

shironury

boootgslkfjdaojfdopsjfopjso
pgjq]pogjopsjg\qrwjopg
j
pogjqwrjgp]oqwjjqw]pjljfojpjowjow4jgopja    ohbip]aeo'rogpoaj0
[bkrw
pojgqwjp\\j\;sync_with_stdiojp
ojeofmpworuc[owejgoprwig
[sdkz
pgj
p[gjes
p0ghjqsp[

jg
prsjgopjg]prwjgoprejgopjrepogjrepog]jgoprejgrgjporeqjgoperjgoprejgopeqrjgopeqrjgoprqwjgpoqjrwsopt4ng\ojsbjsoprnbfqsn\bvhqerpogjorwo
pwewh\rwh \wjiowe orw jop jgr\p jpj o jopj gr\pj p gjop j\pj\pe jp'oj [
 k
 p[eq   fj\pjfdwj\ejopjojopjopjf;'djpfsj, ipojs\p gpsdigsj gorkgjgjrogjdojgiao'fsdvopdshpdfidopcnweojccodj [cjd;ofjd[jdspmcojc"ajno[:Afvoq[w0shbprs`nm/jP{Vadmn;'fnc[Ajojsfpfjcffor 9int i= ; 1 < nfor (int i =1; for (int i =1 ; i <= n: ++i) frfor (int j = 1; j <= ml; ++'}]]]]]]]]]
5
1 5
1 2
2 3
2 4
*/

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6136 KB Output is correct
2 Correct 17 ms 6136 KB Output is correct
3 Correct 18 ms 6288 KB Output is correct
4 Correct 17 ms 6264 KB Output is correct
5 Correct 19 ms 6136 KB Output is correct
6 Correct 18 ms 6136 KB Output is correct
7 Correct 16 ms 6136 KB Output is correct
8 Correct 16 ms 6136 KB Output is correct
9 Correct 15 ms 6136 KB Output is correct
10 Correct 24 ms 6136 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 26204 KB Output is correct
2 Correct 127 ms 25920 KB Output is correct
3 Correct 141 ms 26664 KB Output is correct
4 Correct 126 ms 26196 KB Output is correct
5 Correct 321 ms 25788 KB Output is correct
6 Correct 267 ms 25920 KB Output is correct
7 Correct 145 ms 26024 KB Output is correct
8 Correct 184 ms 25792 KB Output is correct
9 Correct 168 ms 26044 KB Output is correct
10 Correct 328 ms 25920 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 70652 KB Output is correct
2 Correct 467 ms 69368 KB Output is correct
3 Correct 583 ms 72300 KB Output is correct
4 Correct 452 ms 69880 KB Output is correct
5 Execution timed out 1072 ms 69180 KB Time limit exceeded
6 Halted 0 ms 0 KB -