oj.uz

Submission #670817

# Submission time Handle Problem Language Result Execution time Memory
670817 2022-12-10T17:21:09 Z fatemetmhr Palindromes (APIO14_palindrome) C++17
100 / 100
 983 ms 107528 KB 
// ~ Be Name Khoda ~ 
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
 
const int maxn5 = 3e5 + 10;
const int lg    = 19;
const ll  inf   = 1e18;
const int al    = 200;
 
int rnk[lg][maxn5], a[maxn5], lef[maxn5], rig[maxn5];
int val[maxn5], mn[maxn5], lcp[maxn5], rev[maxn5];
int cmpid, lenlen, cmpsz, z[2][maxn5];
set <int> av[2];
vector <int> srt[maxn5];
vector <pair<int, int>> ed;
vector <pair<int, pair<int, int>>> have;
vector <pair<pair<int, int>, int>> req;
 
inline int get_lcp(int v, int u){
    int ans = 0;
    for(int i = lg - 1; i >= 0; i--) if(rnk[i][u] == rnk[i][v]){
        u += (1 << i);
        v += (1 << i);
        ans += (1 << i);
    }
    return ans;
}
 
inline void fix2(int& a){
    if(a < 0)
        a += cmpsz;
    if(a >= cmpsz)
        a -= cmpsz;
}

inline int fix(int a){
    if(a >= cmpsz)
        a -= cmpsz;
    return a;
}
 
inline bool cmp(int i, int j){
    return rnk[cmpid][i] < rnk[cmpid][j] || (rnk[cmpid][i] == rnk[cmpid][j] && rnk[cmpid][fix(i + lenlen)] < rnk[cmpid][fix(j + lenlen)]);
}
 
inline void sort1(int n){
    for(int i = 0; i < max(n, al); i++)
        srt[i].clear();
    for(int i = 0; i < n; i++)
        srt[rnk[cmpid][fix(i + lenlen)]].pb(i);
    int pt = 0;
    for(int i = 0; i < max(n, al); i++)
        for(auto u : srt[i])
            a[pt++] = u;
}
 
inline void sort(){
    int n = cmpsz;
    for(int i = 0; i < n; i++)
        srt[rnk[cmpid][a[i]]].pb(a[i]);
    int pt = 0;
    for(int i = 0; i < max(n, al); i++){
        for(auto u : srt[i])
            a[pt++] = u;
        srt[i].clear();
    }
}
 
inline void build_sf(string s){
    s.pb('#');
    int n = cmpsz = s.size();
    for(int i = 0; i < n; i++){
        rnk[0][i] = int(s[i]);
        srt[rnk[0][i]].pb(i);
    }
    int pt = 0;
    for(int i = 0; i < al; i++) for(auto u : srt[i])
        a[pt++] = u;
    for(int i = 0; i < al; i++)
        srt[i].clear();
    for(int j = 1; j < lg; j++){
        cmpid = j - 1; lenlen = (1 << cmpid) % n;
        for(int i = 0; i < n; i++)
            fix2(a[i] = a[i] - lenlen);
        sort();
        rnk[j][a[0]] = 0;
        for(int i = 1; i < n; i++){
            rnk[j][a[i]] = rnk[j][a[i - 1]] + cmp(a[i - 1], a[i]);
        }
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    string s; cin >> s;
    int n = s.size();
 
    build_sf(s);
    for(int i = 0; i < n; i++)
        a[i] = a[i + 1];
 
    for(int i = 1; i < n; i++){
        lcp[i] = get_lcp(a[i - 1], a[i]);
        ed.pb({lcp[i], i});
    }
    ll ans = 0;
    //cout << t << endl;
    for(int i = 0; i < n; i++){
        //cout << a[i] << ' ';
        rev[a[i]] = i;
        lef[i] = rig[i] = i;
    }
 
    int l = 0, r = 0;
    for(int i = 0; i < n; i++){
        if(i){
            if(r >= i)
                z[1][i] = min(r - i + 1, z[1][r + l - i + 1]);
            while(z[1][i] + i < n && i - z[1][i] - 1 >= 0 && s[i + z[1][i]] == s[i - z[1][i] - 1])
                z[1][i]++;
            have.pb({i - z[1][i], {1, i - 1}});
            ans = max(ans, z[1][i] * 2LL);
            if(i + z[1][i] - 1 > r){
                r = i + z[1][i] - 1;
                l = i - z[1][i];
            }
        }
        if(r >= i)
            z[0][i] = min(r - i + 1, z[0][r + l - i]);
        while(z[0][i] + i < n && i - z[0][i] >= 0 && s[i + z[0][i]] == s[i - z[0][i]])
            z[0][i]++;
        have.pb({i - z[0][i] + 1, {0, i}});
        if(i + z[0][i] - 1 > r){
            r = i + z[0][i] - 1;
            l = i - z[0][i] + 1;
        }
        ans = max(ans, z[0][i] * 2LL - 1);
    }
 
    sort(all(ed));
    while(ed.size()){
        int id = ed.back().se, len = ed.back().fi;
        ed.pop_back();
        int l, r;
        lef[rig[id]] = l = lef[id - 1];
        rig[lef[id - 1]] = r = rig[id];
        req.pb({{a[l], len}, r - l + 1});
    }
 
    sort(all(req));
    sort(all(have));
    int ind = 0;
    //cout << "having " << ans << endl;
 
    for(auto [b, val] : req){
        int l = b.fi, len = b.se;
        //cout << "A request of " << l << ' ' << len << ' ' << val << endl;
        while(ind < have.size() && have[ind].fi <= l){
            av[have[ind].se.fi].insert(have[ind].se.se);
            //cout << "adding " << have[ind].fi << ' ' << have[ind].se.fi << ' ' << have[ind].se.se << endl;
            ind++;
        }
        int klen = len / 2;
        int slen = klen + len % 2;
        auto it = av[0].upper_bound(l + slen - 1);
        if(av[0].size() && it != av[0].begin()){
            it--;
            ans = max(ans, ll(val) * (((*it) - l) * 2 + 1));
            //cout << "well fard " << (*it) << ' ' << ans << endl;
        }
        it = av[1].upper_bound(l + klen - 1);
        if(av[1].size() && it != av[1].begin()){
            it--;
            ans = max(ans, ll(val) * ((*it) - l + 1) * 2);
            //cout << "well zoj " << (*it) << ' ' << ans << endl;
        }
    }
 
    cout << ans << endl;
 
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:169:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         while(ind < have.size() && have[ind].fi <= l){
      |               ~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10832 KB Output is correct
2 Correct 14 ms 10568 KB Output is correct
3 Correct 14 ms 10776 KB Output is correct
4 Correct 14 ms 10720 KB Output is correct
5 Correct 17 ms 10592 KB Output is correct
6 Correct 16 ms 10516 KB Output is correct
7 Correct 15 ms 10596 KB Output is correct
8 Correct 17 ms 10348 KB Output is correct
9 Correct 18 ms 10252 KB Output is correct
10 Correct 18 ms 10460 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 40852 KB Output is correct
2 Correct 125 ms 39428 KB Output is correct
3 Correct 122 ms 40820 KB Output is correct
4 Correct 122 ms 40504 KB Output is correct
5 Correct 153 ms 39112 KB Output is correct
6 Correct 151 ms 40324 KB Output is correct
7 Correct 136 ms 39756 KB Output is correct
8 Correct 212 ms 35660 KB Output is correct
9 Correct 183 ms 36744 KB Output is correct
10 Correct 159 ms 39380 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 95100 KB Output is correct
2 Correct 390 ms 107228 KB Output is correct
3 Correct 386 ms 103868 KB Output is correct
4 Correct 384 ms 104432 KB Output is correct
5 Correct 513 ms 107528 KB Output is correct
6 Correct 447 ms 104548 KB Output is correct
7 Correct 474 ms 104000 KB Output is correct
8 Correct 983 ms 91724 KB Output is correct
9 Correct 943 ms 91880 KB Output is correct
10 Correct 586 ms 102224 KB Output is correct
11 Correct 380 ms 100864 KB Output is correct
12 Correct 909 ms 93328 KB Output is correct