oj.uz

Submission #16072

# Submission time Handle Problem Language Result Execution time Memory
16072 2015-08-15T17:52:39 Z erdemkiraz Palindromes (APIO14_palindrome) C++14
73 / 100
 590 ms 131072 KB 
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
#define hash ___hash

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;

const int N = 3e5 + 5;
const int LOG = 19;
const int P = 29;
const int mod = 1e9 + 7;
const int ODD = 0;
const int EVEN = 1;
const int QU = 2;

int n;
char s[N];

int go_odd[N], go_even[N], pal[N];
ll power[N], hash[N], rhash[N];

class event{ public:
    int x, id, type;
    bool operator<(event oth) const {
        if(x != oth.x)
            return x < oth.x;
        return type < oth.type;
    }
};

inline int get(int x, int y) {
    return (hash[y] + mod - hash[x - 1] * power[y - x + 1] % mod) % mod;
}

inline int rget(int x, int y) {
    return (rhash[x] + mod - rhash[y + 1] * power[y - x + 1] % mod) % mod;
}

void find_pal() {
    power[0] = 1;
    for(int i = 1; i <= n; i++)
        power[i] = power[i - 1] * P % mod;
    for(int i = 1; i <= n; i++)
        hash[i] = (hash[i - 1] * P + s[i] - 'a' + 1) % mod;
    for(int i = n; i >= 1; i--)
        rhash[i] = (rhash[i + 1] * P + s[i] - 'a' + 1) % mod;
    for(int i = 1; i <= n; i++) {
        int l = 1, r = min(i, n - i + 1);
        while(l + 1 < r) {
            int m = (l + r) >> 1;
            if(get(i - m + 1, i) == rget(i, i + m - 1))
                l = m;
            else
                r = m - 1;
        }
        if(get(i - r + 1, i) == rget(i, i + r - 1))
            l = r;
        go_odd[i] = l;
        //printf("go_odd[%d] = %d\n", i, go_odd[i]);
    }
    for(int i = 1; i < n; i++) {
        if(s[i] != s[i + 1])
            continue;
        int l = 1, r = min(i, n - i);
        while(l + 1 < r) {
            int m = (l + r) >> 1;
            if(get(i - m + 1, i) == rget(i + 1, i + m))
                l = m;
            else
                r = m - 1;
        }
        if(get(i - r + 1, i) == rget(i + 1, i + r))
            l = r;
        go_even[i] = l;
        //printf("go_even[%d] = %d\n", i, go_even[i]);
    }
    vector < event > v;
    for(int i = 1; i <= n; i++) {
        v.push_back({i - go_odd[i] + 1, i, ODD});
        if(go_even[i])
            v.push_back({i - go_even[i] + 1, i, EVEN});
        v.push_back({i, i, QU});
    }
    sort(v.begin(), v.end());
    int mx = -1, mx_t = -1;
    foreach(it, v) {
        int x = it -> id;
        int type = it -> type;
        //printf("len = %d x = %d type = %d\n", it -> x, x, type);
        if(type != QU) {
            if(x > mx or (x == mx and type > mx_t)) {
                mx = x;
                mx_t = type;
            }
        }
        else {
            if(mx_t == ODD)
                pal[x] = (mx - x) * 2 + 1;
            else
                pal[x] = (mx - x) * 2 + 2;
        }
    }
    //for(int i = 1; i <= n; i++)
    //    printf("pal[%d] = %d\n", i, pal[i]);
}

int suf[N], order[N], lcp_table[N];
pair < ii, int > p[N];
vector < ii > sort_helper[N];

void fast_sort() {
    for(int i = 1; i <= n; i++)
        sort_helper[p[i].first.second].push_back(ii(p[i].first.first, p[i].second));
    int ptr = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < sort_helper[i].size(); j++)
            p[++ptr] = {{sort_helper[i][j].first, i}, sort_helper[i][j].second};
        sort_helper[i].clear();
    }
    for(int i = 1; i <= n; i++)
        sort_helper[p[i].first.first].push_back(ii(p[i].first.second, p[i].second));
    ptr = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < sort_helper[i].size(); j++)
            p[++ptr] = {{i, sort_helper[i][j].first}, sort_helper[i][j].second};
        sort_helper[i].clear();
    }
}

void one_pass(int k) {
    for(int i = 1; i <= n; i++)
        p[i] = {{suf[i], i + (1 << k) <= n ? suf[i + (1 << k)] : 0}, i};
    fast_sort();
    //sort(p + 1, p + n + 1);
    int ptr = 1;
    for(int i = 1; i <= n; i++) {
        if(i - 1 >= 1 and p[i - 1].first != p[i].first)
            ptr++;
        suf[p[i].second] = ptr;
    }
}

void build_sa() {
    for(int i = 1; i <= n; i++)
        suf[i] = s[i];
    for(int i = 0; i < LOG; i++)
        one_pass(i);
    for(int i = 1; i <= n; i++)
        order[suf[i]] = i;
    //for(int i = 1; i <= n; i++)
    //    printf("order[%d] = %d\n", i, order[i]);
}

void build_lcp() {
    int j = 0;
    for(int i = 1; i <= n; i++) {
        if(suf[i] == 1)
            continue;
        while(i + j <= n and order[suf[i] - 1] + j <= n and s[i + j] == s[order[suf[i] - 1] + j])
            j++;
        lcp_table[suf[i]] = j;
        if(j)
            j--;
    }
    //for(int i = 1; i <= n; i++)
    //    printf("lcp_table[%d] = %d\n", i, lcp_table[i]);
}

int a[N];
ll ans;

void build_table() {
    vector < event > v;
    for(int i = 1; i <= n; i++) {
        v.push_back({i - go_odd[i] + 1, i, ODD});
        if(go_even[i])
            v.push_back({i - go_even[i] + 1, i, EVEN});
        v.push_back({i, i, QU});
    }
    sort(v.begin(), v.end());
    set < int > s1, s2;
    foreach(it, v) {
        int x = it -> id;
        int type = it -> type;
        //printf("len = %d x = %d type = %d\n", it -> x, x, type);
        if(type == ODD)
            s1.insert(x);
        else if(type == EVEN)
            s2.insert(x);
        else {
            int val1 = (lcp_table[suf[x]] + 2 * x - 1) / 2;
            int val2 = (lcp_table[suf[x]] + 2 * x - 2) / 2;
            set < int > :: iterator it = s1.upper_bound(val1);
            if(it != s1.begin()) {
                it--;
                a[suf[x]] = max(a[suf[x]], (*it - x) * 2 + 1);
            }
            if(s2.size()) {
                it = s2.upper_bound(val2);
                if(it != s2.begin()) {
                    it--;
                    a[suf[x]] = max(a[suf[x]], (*it - x) * 2 + 2);
                }
            }
        }
    }
    //for(int i = 1; i <= n; i++)
    //    printf("a[%d] = %d\n", i, a[i]);
}

int sz;
ii vec[N];

void solve() {
    for(int i = 1; i <= n; i++)
        ans = max(ans, (ll) pal[i]);
    build_table();
    for(int i = 2; i <= n + 1; i++) {
        int st = i;
        while(sz and vec[sz - 1].first >= a[i]) {
            ans = max(ans, (ll) (i - vec[sz - 1].second + 1) * vec[sz - 1].first);
            st = vec[sz - 1].second;
            sz--;
        }
        vec[sz++] = ii(a[i], st);
    }
}

int main () {
    
    /*
    n = 3e5;
    
    for(int i = 1; i <= n; i++)
        s[i] = 'a';
    */
    
    scanf("%s", s + 1);
    
    n = strlen(s + 1);
    
    find_pal();
    build_sa();
    build_lcp();
    solve();
    
    printf("%lld\n", ans);
    
    //printf("%.12lf\n", (double) clock() / CLOCKS_PER_SEC);
    
    return 0;
    
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30148 KB Output is correct - answer is '7'
2 Correct 31 ms 30148 KB Output is correct - answer is '4'
3 Correct 27 ms 30148 KB Output is correct - answer is '9'
4 Correct 30 ms 30148 KB Output is correct - answer is '1'
5 Correct 36 ms 30148 KB Output is correct - answer is '1'
6 Correct 27 ms 30148 KB Output is correct - answer is '2'
7 Correct 27 ms 30148 KB Output is correct - answer is '3'
8 Correct 34 ms 30148 KB Output is correct - answer is '3'
9 Correct 27 ms 30148 KB Output is correct - answer is '15'
10 Correct 34 ms 30148 KB Output is correct - answer is '24'
11 Correct 34 ms 30148 KB Output is correct - answer is '10'
12 Correct 30 ms 30148 KB Output is correct - answer is '24'
13 Correct 31 ms 30148 KB Output is correct - answer is '25'
14 Correct 32 ms 30148 KB Output is correct - answer is '28'
15 Correct 35 ms 30148 KB Output is correct - answer is '2'
16 Correct 32 ms 30148 KB Output is correct - answer is '1'
17 Correct 31 ms 30148 KB Output is correct - answer is '15'
18 Correct 28 ms 30148 KB Output is correct - answer is '18'
19 Correct 31 ms 30148 KB Output is correct - answer is '1176'
20 Correct 30 ms 30148 KB Output is correct - answer is '1225'
21 Correct 32 ms 30148 KB Output is correct - answer is '136'
22 Correct 34 ms 30148 KB Output is correct - answer is '45'
23 Correct 30 ms 30148 KB Output is correct - answer is '2500'
24 Correct 31 ms 30148 KB Output is correct - answer is '380'
25 Correct 34 ms 30148 KB Output is correct - answer is '2304'
26 Correct 34 ms 30148 KB Output is correct - answer is '110'
27 Correct 27 ms 30148 KB Output is correct - answer is '93'
28 Correct 30 ms 30148 KB Output is correct - answer is '729'
29 Correct 27 ms 30148 KB Output is correct - answer is '132'
30 Correct 35 ms 30148 KB Output is correct - answer is '7'
31 Correct 26 ms 30148 KB Output is correct - answer is '8'
32 Correct 35 ms 30148 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 30284 KB Output is correct - answer is '124251'
2 Correct 28 ms 30280 KB Output is correct - answer is '38226'
3 Correct 32 ms 30288 KB Output is correct - answer is '249500'
4 Correct 32 ms 30288 KB Output is correct - answer is '5778'
5 Correct 34 ms 30288 KB Output is correct - answer is '247506'
6 Correct 28 ms 30288 KB Output is correct - answer is '248004'
7 Correct 36 ms 30280 KB Output is correct - answer is '973'
8 Correct 28 ms 30284 KB Output is correct - answer is '123753'
9 Correct 28 ms 30284 KB Output is correct - answer is '2346'
10 Correct 34 ms 30148 KB Output is correct - answer is '53'
11 Correct 31 ms 30148 KB Output is correct - answer is '52'
12 Correct 29 ms 30296 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 32908 KB Output is correct - answer is '12497500'
2 Correct 41 ms 32036 KB Output is correct - answer is '6481800'
3 Correct 43 ms 33444 KB Output is correct - answer is '25000000'
4 Correct 54 ms 33268 KB Output is correct - answer is '17816841'
5 Correct 53 ms 32316 KB Output is correct - answer is '9945'
6 Correct 47 ms 32076 KB Output is correct - answer is '504100'
7 Correct 42 ms 32188 KB Output is correct - answer is '1512930'
8 Correct 48 ms 31584 KB Output is correct - answer is '413'
9 Correct 56 ms 31584 KB Output is correct - answer is '428'
10 Correct 51 ms 32224 KB Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 58916 KB Output is correct - answer is '1249925001'
2 Correct 201 ms 53984 KB Output is correct - answer is '396337935'
3 Correct 294 ms 66648 KB Output is correct - answer is '2500050000'
4 Correct 298 ms 64624 KB Output is correct - answer is '1016525689'
5 Correct 235 ms 51904 KB Output is correct - answer is '99645'
6 Correct 213 ms 55284 KB Output is correct - answer is '78569380'
7 Correct 264 ms 57228 KB Output is correct - answer is '82810000'
8 Correct 271 ms 44256 KB Output is correct - answer is '3989'
9 Correct 267 ms 48160 KB Output is correct - answer is '125529616'
10 Correct 272 ms 54992 KB Output is correct - answer is '66664'

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 105776 KB Output is correct - answer is '11250075000'
2 Correct 590 ms 117084 KB Output is correct - answer is '894243195'
3 Memory limit exceeded 509 ms 131072 KB Memory limit exceeded
4 Halted 0 ms 0 KB -