oj.uz

Submission #344494

# Submission time Handle Problem Language Result Execution time Memory
344494 2021-01-06T02:26:25 Z 12tqian Palindromes (APIO14_palindrome) C++17
100 / 100
 594 ms 77556 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define f1r(i, a, b) for (int i = a; i < b; i++) 
#define f0r(i, a) f1r(i, 0, a)
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto& a : x)
typedef string str;
template<class T> struct RMQ { // floor(log_2(x))
    int level(int x) { return 31-__builtin_clz(x); } 
    vector<T> v; vector<vi> jmp;
    int comb(int a, int b) { // index of min
        return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); } 
    void init(const vector<T>& _v) {
        v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
        for (int j = 1; 1<<j <= sz(v); ++j) {
            jmp.pb(vi(sz(v)-(1<<j)+1));
            F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
                                    jmp[j-1][i+(1<<(j-1))]);
        }
    }
    int index(int l, int r) { // get index of min element
        assert(l <= r); int d = level(r-l+1);
        return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
    T query(int l, int r) { return v[index(l,r)]; }
};
struct SuffixArray {
    str S; int N; vi sa, isa, lcp;
    void init(str _S) { N = sz(S = _S)+1; genSa(); genLcp(); }
    void genSa() {
        sa = isa = vi(N); sa[0] = N-1; iota(1+all(sa),0);
        sort(1+all(sa),[&](int a, int b) { return S[a] < S[b]; });
        FOR(i,1,N) { int a = sa[i-1], b = sa[i];
            isa[b] = i > 1 && S[a] == S[b] ? isa[a] : i; }
        for (int len = 1; len < N; len *= 2) { // currently sorted by first len chars
            vi s(sa), is(isa), pos(N); iota(all(pos),0); 
            trav(t,s) { int T = t-len; if (T >= 0) sa[pos[isa[T]]++] = T; }
            FOR(i,1,N) { int a = sa[i-1], b = sa[i];
                isa[b] = is[a] == is[b] && is[a+len] == is[b+len] ? isa[a] : i; }
        }
    }
    void genLcp() { // Kasai's Algo
        lcp = vi(N-1); int h = 0;
        F0R(b,N-1) { int a = sa[isa[b]-1];
            while (a+h < sz(S) && S[a+h] == S[b+h]) h ++;
            lcp[isa[b]-1] = h; if (h) h--; }
        R.init(lcp); /// if we cut off first chars of two strings
        /// with lcp h then remaining portions still have lcp h-1 
    }
    RMQ<int> R; 
    int getLCP(int a, int b) { // lcp of suffixes starting at a,b
        if (a == b) return sz(S)-a;
        int l = isa[a], r = isa[b]; if (l > r) swap(l,r);
        return R.query(l,r-1);
    }
};
 
vi manacher(str s) {
    str s1 = "@"; trav(c,s) s1 += c, s1 += "#";
    s1.back() = '&';
    vi ans(sz(s1)-1); int lo = 0, hi = 0;
    FOR(i,1,sz(s1)-1) {
        if (i != 1) ans[i] = min(hi-i,ans[hi-i+lo]);
        while (s1[i-ans[i]-1] == s1[i+ans[i]+1]) ans[i] ++;
        if (i+ans[i] > hi) lo = i-ans[i], hi = i+ans[i];
    }
    ans.erase(begin(ans));
    F0R(i,sz(ans)) if ((i&1) == (ans[i]&1)) ans[i] ++; 
    return ans;
} 

struct DSU {
    std::vector<int> e;
    std::vector<std::pair<int, int>> interval;
    void init(int n) {
        e = std::vector<int>(n, -1);
        interval.resize(n);
        for (int i = 0; i < n; i++) {
            interval[i].first = interval[i].second = i;
        }
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        interval[x].first = min(interval[x].first, interval[y].first);
        interval[x].second = max(interval[x].second, interval[y].second);
        e[x] += e[y]; e[y] = x;
        return true;
    }
    std::pair<int, int> get_interval(int x) {
        x = get(x);
        return interval[x];
    }
};
 
template <class T> struct BIT {
    std::vector<T> bit;
    int n;
    void init(int n_) {
        n = n_;
        bit.resize(n);
    }
    void init(std::vector<T>& a) {
        n = (int) a.size();
        a.assign(n, 0);
        for (int i = 0; i < (int) a.size(); i++) {
            add(i, a[i]);
        }
    }
    T sum(int r) {
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
        return ret;
    }
    T query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    void add(int idx, T delta) {
        for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
    }
};
int main() {
    cin.tie(0)->sync_with_stdio(0);
    string s; cin >> s;
    int n = sz(s);
    SuffixArray S; S.init(s);
    vi m = manacher(s);
    ll ans = 0;
    for (ll x : m) 
        ans = max(ans, x);
    {
        vi pal(n);
        f0r(i, n) {
            if (i) pal[i] = m[2*i-1] / 2;
        }
        DSU D; D.init(n);
        vector<vi> bucket(n);
        vector<vi> gap(n);
        f0r(i, n) {
            bucket[pal[i]].eb(i);
        }
        f0r(i, n-1) {
            int i1 = S.sa[i+1];
            int i2 = S.sa[i+2];
            int val = S.getLCP(i1, i2);
            gap[val].eb(i);
        }
        set<pi> ranges;
        f0r(i, n) {
            ranges.emplace(i, i);
        }
        BIT<ll> bit;
        bit.init(n);
        for (int i = n-1; i >= 0; i--) {
            // you're checking for palindromes of length
            // 2*i, so you insert in things
            // you check each of the things 
            for (int x : bucket[i]) {
                bit.add(S.isa[x]-1, 1); // add 1 to a potential location
            }
            for (int x : gap[i]) {
                D.unite(x, x+1);
            }
            for (int x : bucket[i]) {
                int y = S.isa[x]-1;
                pi p = D.get_interval(y);
                int res = bit.query(p.f, p.s);
                ans = max(ans, 1LL * 2 * i * res);
            }
        }
    }
    {
        vi pal(n);
        f0r(i, n) {
            pal[i] = m[2*i] / 2;
        }
        vector<vi> bucket(n);
        vector<vi> gap(n);
        f0r(i, n) {
            bucket[pal[i]].eb(i);
        }
        f0r(i, n-1) {
            int i1 = S.sa[i+1];
            int i2 = S.sa[i+2];
            int val = S.getLCP(i1, i2);
            if (val)
                gap[val - 1].eb(i);
        }
        DSU D; D.init(n);
        BIT<ll> bit;
        bit.init(n);
        for (int i = n-1; i >= 0; i--) {
            for (int x : bucket[i]) {
                bit.add(S.isa[x]-1, 1); // add 1 to a potential location
            }
            for (int x : gap[i]) {
                D.unite(x, x+1);
            }
            
            for (int x : bucket[i]) {
                int y = S.isa[x]-1;
                pi p = D.get_interval(y);
                int res = bit.query(p.f, p.s);
                ans = max(ans, 1LL * (2 * i + 1) * res);
            }
        }
;
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2668 KB Output is correct
2 Correct 9 ms 2540 KB Output is correct
3 Correct 10 ms 2668 KB Output is correct
4 Correct 11 ms 2668 KB Output is correct
5 Correct 9 ms 2412 KB Output is correct
6 Correct 9 ms 2412 KB Output is correct
7 Correct 9 ms 2412 KB Output is correct
8 Correct 10 ms 2304 KB Output is correct
9 Correct 9 ms 2284 KB Output is correct
10 Correct 9 ms 2412 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 24336 KB Output is correct
2 Correct 125 ms 22928 KB Output is correct
3 Correct 111 ms 25668 KB Output is correct
4 Correct 106 ms 23824 KB Output is correct
5 Correct 127 ms 22416 KB Output is correct
6 Correct 122 ms 22308 KB Output is correct
7 Correct 109 ms 22288 KB Output is correct
8 Correct 138 ms 21668 KB Output is correct
9 Correct 130 ms 22544 KB Output is correct
10 Correct 132 ms 22672 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 74204 KB Output is correct
2 Correct 347 ms 67700 KB Output is correct
3 Correct 363 ms 77556 KB Output is correct
4 Correct 359 ms 69768 KB Output is correct
5 Correct 507 ms 69108 KB Output is correct
6 Correct 376 ms 68724 KB Output is correct
7 Correct 395 ms 67900 KB Output is correct
8 Correct 567 ms 66548 KB Output is correct
9 Correct 594 ms 66548 KB Output is correct
10 Correct 491 ms 69236 KB Output is correct
11 Correct 353 ms 74484 KB Output is correct
12 Correct 532 ms 67316 KB Output is correct