oj.uz

Submission #887941

# Submission time Handle Problem Language Result Execution time Memory
887941 2023-12-15T14:40:31 Z phong Palindromes (APIO14_palindrome) C++17
100 / 100
 771 ms 73748 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 3e5 + 5;
const ll oo = 1e18;
const int lg = 18;
const int tx = 2;
const ll base = 311;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

ll mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int n, cur = 0;
string s;
ll pw[2][nmax], h[nmax][2];
int D_odd[nmax];
int D_even[nmax];

void Calc_D_odd() {
    int L = 1;
    int R = 0;
    for(int i = 1 ; i <= n; i++) {
        if(i > R) D_odd[i] = 0;
        else D_odd[i] = min(R - i, D_odd[L + (R - i)]);
        while(i - D_odd[i] - 1 > 0 && i + D_odd[i] + 1 <= n && s[i - D_odd[i] - 1] == s[i + D_odd[i] + 1]) {
            D_odd[i]++;
        }

        if(i + D_odd[i] > R) {
            R = i + D_odd[i];
            L = i - D_odd[i];
        }
    }
}

void Calc_D_even() {
    int L = 1;
    int R = 0;
    for(int i = 1 ; i < n; i++) {
        int j = i + 1;
        if(j > R) D_even[i] = 0;
        else D_even[i] = min(R - j + 1, D_even[L + (R - j)]);
        while(i - D_even[i] > 0 && j + D_even[i] <= n && s[i - D_even[i]] == s[j + D_even[i]]) {
            D_even[i]++;
        }
        if(i + D_even[i] > R) {
            R = i + D_even[i];
            L = j - D_even[i];
        }
    }
}


void Init(){
    for(int j = 0; j < tx; ++j) pw[j][0] = 1;
    for(int i = 1, j; i <= n; ++i){
        for(int j = 0; j < tx; ++j){
            pw[j][i] = pw[j][i - 1] * base % mod[j];
            h[i][j] = (h[i - 1][j] * base + s[i] - 'a' + 1) % mod[j];
        }
    }
}
ll get(int l, int r, int ix){
    return (h[r][ix] - h[l - 1][ix] * pw[ix][r - l + 1] + mod[ix] * mod[ix]) % mod[ix];
}

map<pii, bool> mp;
map<pii, int>  ind;
int cnt[nmax], f[nmax];
vector<int> tmp;
vector<int> adj[nmax];

void update(int l, int r){
    bool ok = 1;
    while(l <= r){
        pii x = {get(l, r, 0), get(l, r, 1)};
        if(!mp[x]){
            ind[x] = ++cur;
            tmp.push_back(cur);
            if(ok){
                f[cur]++;
                ok = 0;
            }
            cnt[cur] = r - l + 1;
            mp[x] = 1;
        }
        else{
            int id = ind[x];
            tmp.push_back(id);
            if(ok) f[id]++;

            break;
        }
        ++l, --r;
    }
    if(l > r) tmp.push_back(0);
    int x = (int)tmp.size() - 1;
    for(int i = 0; i < x; ++i){
        int x = tmp[i], y = tmp[i + 1];
        adj[y].push_back(x);
    }
    tmp.clear();
}
void dfs(int u){
    for(auto v : adj[u]){
        dfs(v);
        f[u] += f[v];
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> s;
    n = s.size(); s = ' ' + s + ' ';
    Init();
    Calc_D_odd();
    Calc_D_even();
    for(int i = 1; i <= n; ++i){
        update(i - D_odd[i], i + D_odd[i]);
        if(i < n) update(i - D_even[i] + 1, i + D_even[i]);
    }
    dfs(0);

    ll ans = 0;
    for(int i = 1; i <= cur; ++i){
        ans = max(ans, 1ll * f[i] * cnt[i]);
    }
    cout << ans;
}
/*

*/

Compilation message

palindrome.cpp: In function 'void Init()':
palindrome.cpp:62:20: warning: unused variable 'j' [-Wunused-variable]
   62 |     for(int i = 1, j; i <= n; ++i){
      |                    ^
palindrome.cpp: At global scope:
palindrome.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14776 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14984 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14768 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14984 KB Output is correct
17 Correct 3 ms 14984 KB Output is correct
18 Correct 3 ms 14988 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 3 ms 14940 KB Output is correct
23 Correct 4 ms 14992 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 4 ms 14988 KB Output is correct
27 Correct 4 ms 14948 KB Output is correct
28 Correct 4 ms 14936 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 3 ms 14940 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 4 ms 14940 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 15196 KB Output is correct
4 Correct 4 ms 15136 KB Output is correct
5 Correct 5 ms 14992 KB Output is correct
6 Correct 4 ms 15192 KB Output is correct
7 Correct 4 ms 15196 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14996 KB Output is correct
12 Correct 4 ms 14936 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16728 KB Output is correct
2 Correct 11 ms 16852 KB Output is correct
3 Correct 16 ms 16732 KB Output is correct
4 Correct 13 ms 16728 KB Output is correct
5 Correct 10 ms 16856 KB Output is correct
6 Correct 13 ms 16732 KB Output is correct
7 Correct 14 ms 16732 KB Output is correct
8 Correct 5 ms 15196 KB Output is correct
9 Correct 5 ms 15192 KB Output is correct
10 Correct 8 ms 16216 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 37444 KB Output is correct
2 Correct 145 ms 36976 KB Output is correct
3 Correct 173 ms 37356 KB Output is correct
4 Correct 154 ms 36856 KB Output is correct
5 Correct 115 ms 37308 KB Output is correct
6 Correct 79 ms 32244 KB Output is correct
7 Correct 124 ms 33780 KB Output is correct
8 Correct 17 ms 20480 KB Output is correct
9 Correct 38 ms 24228 KB Output is correct
10 Correct 91 ms 34948 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 73356 KB Output is correct
2 Correct 596 ms 70144 KB Output is correct
3 Correct 771 ms 73340 KB Output is correct
4 Correct 672 ms 70672 KB Output is correct
5 Correct 406 ms 73424 KB Output is correct
6 Correct 504 ms 64788 KB Output is correct
7 Correct 424 ms 62080 KB Output is correct
8 Correct 35 ms 22160 KB Output is correct
9 Correct 33 ms 22380 KB Output is correct
10 Correct 314 ms 64648 KB Output is correct
11 Correct 538 ms 73748 KB Output is correct
12 Correct 61 ms 26776 KB Output is correct