oj.uz

Submission #887945

# Submission time Handle Problem Language Result Execution time Memory
887945 2023-12-15T14:47:05 Z phong Palindromes (APIO14_palindrome) C++17
100 / 100
 716 ms 69200 KB 
#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 = 31;
#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;

int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int n, cur = 0;
string s;
int pw[2][nmax], h[2][nmax];
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] = 1ll * pw[j][i - 1] * base % mod[j];
            h[j][i] = (1ll * h[j][i - 1] * base + s[i] - 'a' + 1) % mod[j];
        }
    }
}
int get(int l, int r, int ix){
    return (h[ix][r] - 1ll * h[ix][l - 1] * pw[ix][r - l + 1] + 1ll * mod[ix] * mod[ix]) % mod[ix];
}

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

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

            break;
        }
        ++l, --r;
    }
    if(l > r) b[++sz] = 0;
    for(int i = 1, x, y; i < sz; ++i){
        x = b[i], y = b[i + 1];
        adj[y].push_back(x);
    }
}
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:59:20: warning: unused variable 'j' [-Wunused-variable]
   59 |     for(int i = 1, j; i <= n; ++i){
      |                    ^
palindrome.cpp: At global scope:
palindrome.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 2 ms 14996 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 2 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 2 ms 14940 KB Output is correct
11 Correct 2 ms 14936 KB Output is correct
12 Correct 2 ms 14940 KB Output is correct
13 Correct 2 ms 14940 KB Output is correct
14 Correct 2 ms 14936 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 2 ms 14940 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 2 ms 14940 KB Output is correct
19 Correct 2 ms 14940 KB Output is correct
20 Correct 2 ms 14936 KB Output is correct
21 Correct 2 ms 14936 KB Output is correct
22 Correct 2 ms 14940 KB Output is correct
23 Correct 2 ms 14940 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 2 ms 14940 KB Output is correct
27 Correct 2 ms 14940 KB Output is correct
28 Correct 3 ms 14936 KB Output is correct
29 Correct 3 ms 15096 KB Output is correct
30 Correct 2 ms 14940 KB Output is correct
31 Correct 2 ms 14936 KB Output is correct
32 Correct 3 ms 14936 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 14940 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 15008 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14948 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16732 KB Output is correct
2 Correct 10 ms 16732 KB Output is correct
3 Correct 12 ms 16756 KB Output is correct
4 Correct 15 ms 16732 KB Output is correct
5 Correct 9 ms 16732 KB Output is correct
6 Correct 9 ms 16732 KB Output is correct
7 Correct 10 ms 16552 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 7 ms 15964 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 33012 KB Output is correct
2 Correct 137 ms 32400 KB Output is correct
3 Correct 160 ms 33012 KB Output is correct
4 Correct 166 ms 32544 KB Output is correct
5 Correct 96 ms 32568 KB Output is correct
6 Correct 73 ms 27808 KB Output is correct
7 Correct 111 ms 29356 KB Output is correct
8 Correct 15 ms 16264 KB Output is correct
9 Correct 38 ms 19968 KB Output is correct
10 Correct 78 ms 30196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 69000 KB Output is correct
2 Correct 548 ms 66184 KB Output is correct
3 Correct 716 ms 69200 KB Output is correct
4 Correct 646 ms 66740 KB Output is correct
5 Correct 366 ms 68576 KB Output is correct
6 Correct 462 ms 61004 KB Output is correct
7 Correct 419 ms 58140 KB Output is correct
8 Correct 32 ms 18484 KB Output is correct
9 Correct 33 ms 18508 KB Output is correct
10 Correct 305 ms 60044 KB Output is correct
11 Correct 457 ms 69000 KB Output is correct
12 Correct 60 ms 22916 KB Output is correct