oj.uz

답안 #916358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916358 2024-01-25T18:02:08 Z Alcabel 회문 (APIO14_palindrome) C++17
100 / 100
 801 ms 14980 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7, p = 31, maxn = 3e5 + 1;

struct Modint {
    int x;
    Modint() { x = 0; }
    Modint(int _x) {
        while (_x >= mod) { _x -= mod; }
        while (_x < 0) { _x += mod; }
        x = _x;
    }
    Modint(long long _x) {
        if (_x >= mod || _x <= -mod) { _x %= mod; }
        if (_x < 0) { _x += mod; }
        x = _x;
    }
    Modint operator+(const Modint& other) const {
        return Modint(x + other.x);
    }
    Modint operator-(const Modint& other) const {
        return Modint(x - other.x);
    }
    Modint operator*(const Modint& other) const {
        return Modint(x * 1ll * other.x);
    }
    void operator+=(const Modint& other) {
        *this = *this + other;
    }
    void operator-=(const Modint& other) {
        *this = *this - other;
    }
    void operator*=(const Modint& other) {
        *this = *this * other;
    }
    ~Modint() {}
};

Modint pExp[maxn];

struct DSU {
    int n, maxcompsz;
    vector<int> par, sz;
    DSU() {}
    DSU(int _n) {
        n = _n, maxcompsz = 0;
        par.resize(n);
        sz.resize(n);
        clear();
    }
    void clear() {
        maxcompsz = 0;
        for (int i = 0; i < n; ++i) {
            par[i] = -1, sz[i] = 0;
        }
    }
    void create(int i) {
        par[i] = i, sz[i] = 1;
        maxcompsz = max(maxcompsz, 1);
    }
    int getParent(int v) {
        if (par[v] != v) {
            par[v] = getParent(par[v]);
        }
        return par[v];
    }
    void uniteSets(int v, int u) {
        v = getParent(v), u = getParent(u);
        if (v == u) {
            return;
        }
        sz[v] += sz[u];
        par[u] = v;
        maxcompsz = max(maxcompsz, sz[v]);
    }
    ~DSU() {}
};

int posOf[maxn];

void countSort(vector<int>& a, vector<int>& tmp, const vector<int>& c) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        posOf[i] = 0;
    }
    for (const int& x : c) {
        ++posOf[x];
    }
    for (int i = n - 1, pref = n; i >= 0; --i) {
        pref -= posOf[i];
        posOf[i] = pref;
    }
    for (const int& x : a) {
        tmp[posOf[c[x]]++] = x;
    }
    swap(a, tmp);
}

void buildSufArr(const string& s, vector<int>& sufArr, vector<int>& c) {
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        sufArr[i] = i;
    }
    sort(sufArr.begin(), sufArr.end(), [&](const int& A, const int& B) {
        return s[A] < s[B];
    });
    c[sufArr[0]] = 0;
    for (int i = 1; i < n; ++i) {
        c[sufArr[i]] = c[sufArr[i - 1]];
        if (s[sufArr[i - 1]] != s[sufArr[i]]) {
           ++c[sufArr[i]];
        }
    }
    vector<int> tmp(n);
    for (int k = 0; (1 << k) < n; ++k) {
        for (int i = 0; i < n; ++i) {
            sufArr[i] -= (1 << k);
            if (sufArr[i] < 0) {
                sufArr[i] += n;
            }
        }
        countSort(sufArr, tmp, c);
        tmp[sufArr[0]] = 0;
        for (int i = 1; i < n; ++i) {
            tmp[sufArr[i]] = tmp[sufArr[i - 1]];
            int nxtprev = sufArr[i - 1] + (1 << k);
            if (nxtprev >= n) { nxtprev -= n; }
            int nxtcur = sufArr[i] + (1 << k);
            if (nxtcur >= n) { nxtcur -= n; }
            if (c[sufArr[i - 1]] != c[sufArr[i]] || c[nxtprev] != c[nxtcur]) {
                ++tmp[sufArr[i]];
            }
        }
        swap(c, tmp);
    }
}

vector<Modint> h, revH;
string s;

bool equalOne(int l1, int r1, int l2, int r2) {
    int val1 = ((h[r1 + 1] - h[l1]) * pExp[(int)h.size() - 2 - r1]).x;
    int val2 = ((h[r2 + 1] - h[l2]) * pExp[(int)h.size() - 2 - r2]).x;
    return val1 == val2;
}

int getLcp(int i, int j) {
    int left = 0, right = (int)s.size() - max(i, j); 
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (equalOne(i, i + mid - 1, j, j + mid - 1)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left;
}

/*void buildLcp(const string& s, vector<int>& sufArr, vector<int>& c, vector<int>& lcp) {
    lcp[0] = 0;
    for (int i = 1; i < (int)s.size() - 1; ++i) {
        int ptr = sufArr[i], j = sufArr[i + 1];
        int left = 0, right = (int)s.size() - max(ptr, j);
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (equalOne(ptr, ptr + mid - 1, j, j + mid - 1)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        lcp[i] = left;
    }
}*/

bool equal(int l1, int r1, int l2, int r2) {
    int val1 = ((h[r1 + 1] - h[l1]) * pExp[(int)h.size() - 2 - r1]).x;
    int val2 = ((revH[l2] - revH[r2 + 1]) * pExp[l2]).x;
    return val1 == val2;
}

//sparse Table

void solve() {
    cin >> s;
    int n = s.size();
    h.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        h[i + 1] = h[i] + pExp[i] * (s[i] - 'a' + 1);
    }
    revH.resize(n + 1);
    for (int i = n - 1; i >= 0; --i) {
        revH[i] = revH[i + 1] + pExp[n - 1 - i] * (s[i] - 'a' + 1);
        // cerr << "i: " << i << ", revH: " << revH[i].x << '\n';
    }
    vector<int> odd(n), even(n);
    // even
    for (int i = 0; i < n; ++i) {
        int left = 0, right = min(i, n - i) + 1;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (equal(i - mid, i - 1, i, i + mid - 1)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        even[i] = left;
        // cerr << "i: " << i << ", even: " << even[i] << '\n';
    }
    // odd
    for (int i = 0; i < n; ++i) {
        int left = 0, right = min(i + 1, n - i) + 1;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (equal(i - mid + 1, i, i, i + mid - 1)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        odd[i] = left;
        // cerr << "i: " << i << ", odd: " << odd[i] << '\n';
    }
    s += '#';
    ++n;
    vector<int> sufArr(n), c(n);
    buildSufArr(s, sufArr, c);
    /*for (int i = 0; i < n; ++i) {
        cerr << sufArr[i] << ' ';
    }
    cerr << '\n';
    for (int i = 0; i < n; ++i) {
        cerr << c[i] << ' ';
    }
    cerr << '\n';*/
    vector<pair<int, int>> evs(n - 1);
    long long ans = 0;
    DSU dsu(n);
    set<int> alive;
    // even lengths
    for (int i = 0; i < n - 1; ++i) {
        evs[i] = {2 * even[i], i};
    }
    sort(evs.rbegin(), evs.rend());
    for (int len = n / 2 * 2, ptr = 0; len > 0; len -= 2) {
        while (ptr < (int)evs.size() && evs[ptr].first == len) {
            int i = evs[ptr].second;
            // cerr << "i: " << i << '\n';
            // cerr << "c: " << c[i] << '\n';
            dsu.create(i);
            auto it = alive.emplace(c[i]).first;
            if (it != alive.begin()) {
                auto prv = prev(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*prv] << '\n';
                while (getLcp(sufArr[*prv], i) * 2 >= len) {
                    // cerr << "merge: " << *prv << '\n';
                    dsu.uniteSets(i, sufArr[*prv]);
                    prv = alive.erase(prv);
                    if (prv == alive.begin()) {
                        break;
                    } else {
                        prv = prev(prv);
                    }
                }
            }
            if (*it != *alive.rbegin()) {
                auto nxt = next(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*nxt] << '\n';
                while (getLcp(sufArr[*nxt], i) * 2 >= len) {
                    dsu.uniteSets(i, sufArr[*nxt]);
                    nxt = alive.erase(nxt);
                    if (nxt == alive.end()) {
                        break;
                    }
                }
            }
            ++ptr;
        }
        // cerr << "len: " << len << ", sz: " << dsu.maxcompsz << '\n';
        ans = max(ans, dsu.maxcompsz * 1ll * len);
    }
    // odd lengths
    dsu.clear();
    alive.clear();
    for (int i = 0; i < n - 1; ++i) {
        evs[i] = {2 * odd[i] - 1, i};
    }
    sort(evs.rbegin(), evs.rend());
    for (int len = (n % 2 == 0 ? n - 1 : n), ptr = 0; len > 0; len -= 2) {
        while (ptr < (int)evs.size() && evs[ptr].first == len) {
            int i = evs[ptr].second;
            dsu.create(i);
            auto it = alive.emplace(c[i]).first;
            if (it != alive.begin()) {
                auto prv = prev(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*prv] << '\n';
                while (getLcp(sufArr[*prv], i) * 2 - 1 >= len) {
                    // cerr << "merge: " << *prv << '\n';
                    dsu.uniteSets(i, sufArr[*prv]);
                    prv = alive.erase(prv);
                    if (prv == alive.begin()) {
                        break;
                    } else {
                        prv = prev(prv);
                    }
                }
            }
            if (*it != *alive.rbegin()) {
                auto nxt = next(it);
                // cerr << "i: " << i << ", sufArr: " << sufArr[*nxt] << '\n';
                while (getLcp(sufArr[*nxt], i) * 2 - 1 >= len) {
                    dsu.uniteSets(i, sufArr[*nxt]);
                    nxt = alive.erase(nxt);
                    if (nxt == alive.end()) {
                        break;
                    }
                }
            }
            ++ptr;
        }
        // cerr << "len: " << len << ", sz: " << dsu.maxcompsz << '\n';
        ans = max(ans, dsu.maxcompsz * 1ll * len);
    }
    cout << ans << '\n';
    /*vector<int> lcp(n - 1);
    buildLcp(s, sufArr, c, lcp);*/
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    pExp[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        pExp[i] = pExp[i - 1] * p;
    }

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2396 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 2 ms 2396 KB Output is correct
20 Correct 3 ms 2392 KB Output is correct
21 Correct 2 ms 2652 KB Output is correct
22 Correct 2 ms 2652 KB Output is correct
23 Correct 2 ms 2648 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2396 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2396 KB Output is correct
29 Correct 2 ms 2648 KB Output is correct
30 Correct 2 ms 2392 KB Output is correct
31 Correct 2 ms 2648 KB Output is correct
32 Correct 2 ms 2652 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2648 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2908 KB Output is correct
2 Correct 14 ms 2908 KB Output is correct
3 Correct 14 ms 2908 KB Output is correct
4 Correct 15 ms 3116 KB Output is correct
5 Correct 14 ms 2904 KB Output is correct
6 Correct 14 ms 2908 KB Output is correct
7 Correct 15 ms 2904 KB Output is correct
8 Correct 16 ms 2904 KB Output is correct
9 Correct 18 ms 3072 KB Output is correct
10 Correct 18 ms 3176 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 6856 KB Output is correct
2 Correct 154 ms 6872 KB Output is correct
3 Correct 152 ms 6856 KB Output is correct
4 Correct 191 ms 6936 KB Output is correct
5 Correct 194 ms 6908 KB Output is correct
6 Correct 177 ms 6856 KB Output is correct
7 Correct 215 ms 6944 KB Output is correct
8 Correct 182 ms 6852 KB Output is correct
9 Correct 174 ms 6940 KB Output is correct
10 Correct 224 ms 7104 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 476 ms 14784 KB Output is correct
2 Correct 561 ms 14980 KB Output is correct
3 Correct 497 ms 14836 KB Output is correct
4 Correct 763 ms 14916 KB Output is correct
5 Correct 627 ms 14656 KB Output is correct
6 Correct 646 ms 14660 KB Output is correct
7 Correct 742 ms 14660 KB Output is correct
8 Correct 617 ms 14872 KB Output is correct
9 Correct 613 ms 14920 KB Output is correct
10 Correct 801 ms 14664 KB Output is correct
11 Correct 465 ms 14776 KB Output is correct
12 Correct 602 ms 14920 KB Output is correct