oj.uz

Submission #887954

# Submission time Handle Problem Language Result Execution time Memory
887954 2023-12-15T15:25:11 Z phong Palindromes (APIO14_palindrome) C++17
100 / 100
 668 ms 73896 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];
        }
    }
}
int 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<ll, bool> mp;
map<ll, int>  ind;
int cnt[nmax], f[nmax], b[nmax];
vector<int> adj[nmax];

void update(int l, int r){
    bool ok = 1;int sz = 0;
    while(l <= r){
        ll x = 1ll * get(l, r, 0) * (1ll << 32) + 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:62:20: warning: unused variable 'j' [-Wunused-variable]
   62 |     for(int i = 1, j; i <= n; ++i){
      |                    ^
palindrome.cpp: At global scope:
palindrome.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18668 KB Output is correct
2 Correct 12 ms 18780 KB Output is correct
3 Correct 12 ms 18788 KB Output is correct
4 Correct 12 ms 18776 KB Output is correct
5 Correct 9 ms 18780 KB Output is correct
6 Correct 9 ms 18820 KB Output is correct
7 Correct 11 ms 18780 KB Output is correct
8 Correct 5 ms 17244 KB Output is correct
9 Correct 4 ms 17244 KB Output is correct
10 Correct 7 ms 18268 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 35700 KB Output is correct
2 Correct 163 ms 35064 KB Output is correct
3 Correct 157 ms 35572 KB Output is correct
4 Correct 142 ms 35208 KB Output is correct
5 Correct 82 ms 35064 KB Output is correct
6 Correct 69 ms 30456 KB Output is correct
7 Correct 95 ms 31992 KB Output is correct
8 Correct 15 ms 18688 KB Output is correct
9 Correct 36 ms 22520 KB Output is correct
10 Correct 91 ms 32788 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 73860 KB Output is correct
2 Correct 533 ms 71084 KB Output is correct
3 Correct 668 ms 73896 KB Output is correct
4 Correct 610 ms 71568 KB Output is correct
5 Correct 349 ms 73348 KB Output is correct
6 Correct 495 ms 65444 KB Output is correct
7 Correct 431 ms 62852 KB Output is correct
8 Correct 35 ms 23188 KB Output is correct
9 Correct 34 ms 23276 KB Output is correct
10 Correct 293 ms 64716 KB Output is correct
11 Correct 472 ms 73792 KB Output is correct
12 Correct 63 ms 27768 KB Output is correct