oj.uz

Submission #848979

# Submission time Handle Problem Language Result Execution time Memory
848979 2023-09-13T19:14:17 Z treap_enjoyer Palindromes (APIO14_palindrome) C++14
100 / 100
 820 ms 48284 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;


const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;

int n;
string s;
vector<ll> h;
vector<ll> p;
vector<int> d1;
vector<int> d2;
vector<int> arr;
void calc(){
    h.resize(n + 1);
    p.resize(n + 1, 1);
    for(int i = 1; i < n; i++){
        p[i] *= p[i - 1];
        p[i] *= 31;
        p[i] %= INF;
    }
    for(int i = 0; i < n; i++){
        if(i) h[i] += h[i - 1];
        h[i] += (s[i] - 'a' + 1) * p[i];
        h[i] %= INF;
    }
}
void man(){
    d1.resize(n, 0);
    d2.resize(n, 0);
    int l = 0, r = -1;
    for(int i = 0; i < n; i++){
        int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
        while(i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if(i + k - 1 > r){
            r = i + k - 1;
            l = i - k + 1;
        }
    }
    l = 0, r = -1;
    for(int i = 0; i < n; i++){
        int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while(i - k - 1 >= 0 && i + k < n && s[i + k] == s[i - k - 1]) k++;
        d2[i] = k;
        if(i + k - 1 > r){
            l = i - k, r = i + k - 1;
        }
    }
}
void sufmas(){
    arr.resize(n + 1);
    vector<int> c(n + 1, 0);
    vector<int> c1(n + 1);
    vector<int> arr1(n + 1);
    s += '#';
    map<int, vector<int> > cnt;
    for(int i = 0; i <= n; i++){
        cnt[s[i] - 'a'].push_back(i);
    }
    int sch = 0; 
    int sch1 = 0;
    for(auto i: cnt){
        for(auto j: i.second){
            arr[sch] = j;
            c[j] = sch1;
            sch++;
        }
        if(i.second.size()) sch1++;
    }
    cnt.clear();
    vector<vector<int> > q(n + 1);
    for(int k = 0; k < 19; k++){
        for(int i = 0; i <= n; i++){
            //cout << (arr[i] + (1 << k)) % (n + 1) << " " << c[(arr[i] + (1 << k)) % (n + 1)] << endl;
            q[c[(arr[i] + (1 << k)) % (n + 1)]].push_back(arr[i]);
        }
        sch = 0;
        for(int i = 0; i <= n; i++){
            for(auto j: q[i]){
                arr1[sch] = j;
                sch++;
            }
            q[i].clear();
        }
        arr.swap(arr1);
        for(int i = 0; i <= n; i++){
            q[c[arr[i]]].push_back(arr[i]);
        }
        sch = 0;
        for(int i = 0; i <= n; i++){
            for(auto j: q[i]){
                arr1[sch] = j;
                sch++;
            }
            q[i].clear();
        }
        arr.swap(arr1);
        c1[arr[0]] = 0;
        sch = 0;
        int a1, a2, b1, b2;
        for(int i = 1; i <= n; i++){
            a1 = c[arr[i]];
            a2 = c[arr[i - 1]];
            b1 = c[(arr[i] + (1 << k)) % (n + 1)];
            b2 = c[(arr[i - 1] + (1 << k)) % (n + 1)];
            if(a1 != a2 || b1 != b2) sch++;
            c1[arr[i]] = sch;
        }
        c.swap(c1);
    }
}
bool cmp(int a, int b, int cnt){
    if(a + cnt > n || b + cnt > n) return 0;
    ll h1 = h[a + cnt - 1];
    ll h2 = h[b + cnt - 1];
    if(a) h1 = (h1 - h[a - 1] + INF) % INF;
    if(b) h2 = (h2 - h[b - 1] + INF) % INF;
    if(b > a) h1 = (h1 * 1LL * p[b - a]) % INF;
    if(a > b) h2 = (h2 * 1LL * p[a - b]) % INF;
    return h1 == h2;
}
int bin_search(int pos, int cnt){
    if(cnt == 0) return 0;
    int l = 1, r = pos;
    int l1 = 0, r1 = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        if(cmp(arr[mid], arr[pos], cnt)){
            l1 = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    l = pos, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(cmp(arr[mid], arr[pos], cnt)){
            r1 = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    return r1 - l1 + 1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    cin >> s;
    n = s.size();
    calc();
    man();
    sufmas();
    vector<int> c(n + 1, 0);
    for(int i = 1; i <= n; i++){
        c[arr[i]] = i;
    }
    /*for(int i = 1; i <= n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;*/
    ll ans = 0;
    for(int i = 0; i < n; i++){
       // cout << i << " " << d1[i] << " " << d2[i] << " " << c[i - d1[i] + 1] << " " << c[i - d2[i]] << " ----> " << bin_search(c[i - d1[i] + 1], d1[i] * 2 - 1) << " " << bin_search(c[i - d2[i]], d2[i] * 2) << endl;
        ans = max(ans, (d1[i] * 2 - 1) * 1LL * bin_search(c[i - d1[i] + 1], d1[i] * 2 - 1));
        ans = max(ans, (d2[i] * 2) * 1LL * bin_search(c[i - d2[i]], d2[i] * 2));
    }
    cout << ans << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1880 KB Output is correct
2 Correct 7 ms 1624 KB Output is correct
3 Correct 7 ms 1884 KB Output is correct
4 Correct 7 ms 1620 KB Output is correct
5 Correct 9 ms 1624 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 7 ms 1624 KB Output is correct
8 Correct 9 ms 1368 KB Output is correct
9 Correct 10 ms 1368 KB Output is correct
10 Correct 10 ms 1628 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 15680 KB Output is correct
2 Correct 64 ms 14520 KB Output is correct
3 Correct 70 ms 16044 KB Output is correct
4 Correct 83 ms 15472 KB Output is correct
5 Correct 140 ms 14280 KB Output is correct
6 Correct 121 ms 15700 KB Output is correct
7 Correct 99 ms 15308 KB Output is correct
8 Correct 151 ms 11112 KB Output is correct
9 Correct 127 ms 11824 KB Output is correct
10 Correct 144 ms 14656 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 38368 KB Output is correct
2 Correct 224 ms 46524 KB Output is correct
3 Correct 213 ms 48284 KB Output is correct
4 Correct 268 ms 44364 KB Output is correct
5 Correct 556 ms 46908 KB Output is correct
6 Correct 362 ms 44620 KB Output is correct
7 Correct 364 ms 43936 KB Output is correct
8 Correct 711 ms 32040 KB Output is correct
9 Correct 820 ms 32044 KB Output is correct
10 Correct 594 ms 42468 KB Output is correct
11 Correct 241 ms 44824 KB Output is correct
12 Correct 638 ms 33528 KB Output is correct