oj.uz

Submission #99335

# Submission time Handle Problem Language Result Execution time Memory
99335 2019-03-02T17:03:55 Z Akashi Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 53752 KB 
#include <bits/stdc++.h>
using namespace std;

struct usu{
    int x, y, p;
    bool operator < (const usu &aux)const{
        if(x != aux.x) return x < aux.x;
        if(y != aux.y) return y < aux.y;
        return p < aux.p;
    }
};
usu L[300005];

int n, lgn;
char s[300005], T[600005];
int P[20][300005], RMQ[20][300005];
int LP[600005];
int lg[300005], SA[300005];

void build_suffix_array(){
    for(int i = 1; i <= n ; ++i) P[0][i] = s[i] - 'a' + 1;

    for(int k = 1; k <= lgn ; ++k){
        for(int i = 1; i <= n ; ++i)
            L[i] = {P[k - 1][i], ((i + (1 << (k - 1))) <= n) ? P[k - 1][i + (1 << (k - 1))] : -1, i};

        sort(L + 1, L + n + 1);
        P[k][L[1].p] = 1;
        for(int i = 2; i <= n ; ++i){
            if(L[i].x == L[i - 1].x && L[i].y == L[i - 1].y) P[k][L[i].p] = P[k][L[i - 1].p];
            else P[k][L[i].p] = i;
        }
        if(k == lgn){
            int NR = 0;
            SA[++NR] = L[1].p;
            for(int i = 2; i <= n ; ++i) SA[++NR] = L[i].p;
        }
    }
}

inline int find_lcp(int x, int y){
    int ans = 0;
    for(int k = lgn; k >= 0 ; --k){
        if(max(x + ans, y + ans) > n) continue ;
        if(P[k][x + ans] == P[k][y + ans]) ans += (1 << k);
    }
    return ans;
}

void build_lcp(){
    for(int i = 1; i < n ; ++i) RMQ[0][i] = find_lcp(SA[i], SA[i + 1]);

    for(int k = 1; k <= lgn ; ++k)
        for(int i = 1; i <= n - (1 << k) ; ++i) RMQ[k][i] = min(RMQ[k - 1][i], RMQ[k - 1][i + (1 << (k - 1))]);
}
inline int use_lcp(int x, int y){
    if(x == y) return n - x + 1;

    x = P[lgn][x], y = P[lgn][y];
    if(x > y) swap(x, y);

    int l = y - x, k = lg[l];
    return min(RMQ[k][x], RMQ[k][y - (1 << k)]);
}
inline int nrap(int x, int y){
    int st = 1, dr = P[lgn][x] - 1, Sol1 = 0, Sol2 = 0;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(use_lcp(x, SA[mij]) >= y - x + 1){
            Sol1 = max(P[lgn][x] - mij, Sol1);
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    if(use_lcp(x, SA[st]) >= y - x + 1) Sol1 = max(Sol1, P[lgn][x] - st);

    st = P[lgn][x] + 1, dr = n;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(use_lcp(x, SA[mij]) >= y - x + 1){
            Sol2 = max(Sol2, mij - P[lgn][x]);
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    if(use_lcp(x, SA[dr]) >= y - x + 1) Sol2 = max(Sol2, dr - P[lgn][x]);
    return Sol1 + Sol2 + 1;
}
int main()
{
//    freopen("palindrome.in", "r", stdin);
//    freopen("palindrome.out", "w", stdout);

    lg[1] = 0;
    for(int i = 2; i <= 300000 ; ++i) lg[i] = lg[i / 2] + 1;

    scanf("%s", s + 1);
    n = strlen(s + 1);
    lgn = 19;

    build_suffix_array();
    build_lcp();

    ///manacher-sama
    int NR = 0;
    T[++NR] = '.';
    for(int i = 1; i <= n ; ++i) T[++NR] = s[i], T[++NR] = '.';

    int R = 0, C = 0;
    long long Sol = 0;
    for(int i = 1; i <= NR ; ++i){
        int rad = 0;
        if(i <= R) rad = min(R - i, LP[2 * C - i]) + 1;

        while(i + rad < NR && i - rad > 0 && T[i + rad] == T[i - rad]){
            if((i + rad) % 2 == 0) Sol = max(Sol, 1LL * (rad + 1) * nrap((i - rad) / 2, (i + rad) / 2));
            ++rad;
        }
        LP[i] = rad - 1;
        if(i + rad - 1 > R){
            R = i + rad - 1;
            C = i;
        }
    }
    printf("%lld", Sol);

    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3328 KB Output is correct
2 Correct 18 ms 3328 KB Output is correct
3 Correct 22 ms 3192 KB Output is correct
4 Correct 25 ms 3328 KB Output is correct
5 Correct 30 ms 3200 KB Output is correct
6 Correct 23 ms 3192 KB Output is correct
7 Correct 17 ms 3328 KB Output is correct
8 Correct 24 ms 3328 KB Output is correct
9 Correct 25 ms 3328 KB Output is correct
10 Correct 28 ms 3328 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 18496 KB Output is correct
2 Correct 156 ms 18424 KB Output is correct
3 Correct 262 ms 18524 KB Output is correct
4 Correct 189 ms 18424 KB Output is correct
5 Correct 478 ms 18684 KB Output is correct
6 Correct 286 ms 18568 KB Output is correct
7 Correct 241 ms 18424 KB Output is correct
8 Correct 389 ms 18564 KB Output is correct
9 Correct 380 ms 18592 KB Output is correct
10 Correct 438 ms 18632 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 53508 KB Output is correct
2 Correct 538 ms 53752 KB Output is correct
3 Correct 968 ms 53496 KB Output is correct
4 Correct 687 ms 53616 KB Output is correct
5 Execution timed out 1067 ms 51804 KB Time limit exceeded
6 Halted 0 ms 0 KB -