Submission #344488

#	Time	Username	Problem	Language	Result	Execution time	Memory
344488		12tqian	Palindromes (APIO14_palindrome)	C++17	73 / 100	1068 ms	74168 KiB

palindrome

#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;
} 

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;
    // take care of palindromes that occur exactly once
    // We'll consider PAL the 'extension'
    for (ll x : m) ans = max(ans, x);
    {
        // handle even palindromes
        // even length palindrome
        // say loc i, len L
        // consider a contiguous array in suffix array
        // [l, r]
        // Say they have lcp of x
        // min(x, min(PAL [l, r])) * 2 * (r - l + 1)
        // each thing has in common at most x
        // and each loc has palinndrome size at most PAL
        // replace with inner splices, set to min(lcp, PAL[i, i+1]) * 2
        // maximize min(l, r) * (r - l + 1) is the new problem?
        // check the min gap
        // and bash
        // okay that works
        vi pal(n);
        f0r(i, n) {
            if (i) pal[i] = m[2*i-1] / 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);
            gap[val].eb(i);
        }
        set<pi> ranges;
        f0r(i, n) {
            ranges.emplace(i, i);
        }
        auto get = [&](int x) -> pi {
            auto it = ranges.lower_bound({x+1, -1});
            if (it == ranges.begin()) return {-1, -1};
            it = prev(it);
            if (it->f <= x && x <= it->s) return *it;
            return {-1, -1};
        };
        auto link = [&](int x) {
            pi p1 = get(x);
            pi p2 = get(x+1);
            ranges.erase(p1);
            ranges.erase(p2);
            ranges.emplace(p1.f, p2.s);
        };
        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]) {
                // links x, x+1
                link(x);
            }
            for (int x : bucket[i]) {
                int y = S.isa[x]-1;
                // find which bucket y is in
                pi p = get(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);
        }
        set<pi> ranges;
        f0r(i, n) {
            ranges.emplace(i, i);
        }
        auto get = [&](int x) -> pi {
            auto it = ranges.lower_bound({x+1, -1});
            return *prev(it);
        };
        auto link = [&](int x) {
            pi p1 = get(x);
            pi p2 = get(x+1);
            ranges.erase(p1);
            ranges.erase(p2);
            ranges.emplace(p1.f, p2.s);
        };
        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]) {
                // cout << "BUCKET " << x << " " << S.isa[x] << endl;
                bit.add(S.isa[x]-1, 1); // add 1 to a potential location
            }
            for (int x : gap[i]) {
                // links x, x+1
                // cout << "LINK " << x << endl;
                link(x);
            }
            
            for (int x : bucket[i]) {
                int y = S.isa[x]-1;
                // find which bucket y is in
                pi p = get(y);
                int res = bit.query(p.f, p.s);
                // if (i == 1) {
                //     cout << "QUERY " << p.f << " " << p.s << endl;
                // }
                ans = max(ans, 1LL * (2 * i + 1) * res);
            }
        }
        // f0r(i, n) {
        //     cout << S.sa[i+1] << " ";
        // }
        // cout << endl;
        // f0r(i, n) {
        //     cout << S.isa[i] << " " ;
        // }
        // cout << endl;
    }
    cout << ans << '\n';
    return 0;
}

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