Submission #618327

#	Time	Username	Problem	Language	Result	Execution time	Memory
618327		Je_O	Palinilap (COI16_palinilap)	C++17	0 / 100	84 ms	25660 KiB

palinilap

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const int MOD = 420691273;
ll add[N][26];
ll prv[N];
ll pw[N];
ll pw2[N];
ll p[N];
ll pref[N];
ll suff[N];
ll diff[N];
ll diff2[N];

int n;
string s;

ll get_pref(int l, int r){
    if(l == 0)return pref[r];
    return ((pref[r] - pref[l - 1]) % MOD + MOD) % MOD;
}

ll get_suff(int l, int r){
    return ((suff[l] - suff[r + 1]) % MOD + MOD) % MOD;
}

int find_range(int &lf, int &rg, bool b){
    if(min(lf, n - 1 - rg) < 0)return 0;
    if(s[lf] != s[rg])return 0;
    int l = 0, r = min(lf, n - 1 - rg);
    // cout << l << ' ' << r << endl;
    // cout << lf << ' ' << rg << '\n';
    while(l < r){
        int m = (l + r + 1)/2;
        if(get_pref(lf - m, rg + m) * pw[(n - 1) - (rg + m)] % MOD == get_suff(lf - m, rg + m) * pw[lf - m] % MOD)l = m;
        else r = m - 1;
    }
    //cout << l << endl;
    ++l;
    lf -= l; rg += l;
    return l;
}

int get_range(int lf, int rg){
    if(min(lf, n - 1 - rg) < 0)return 0;
    int l = 0, r = min(lf, n - 1 - rg);
    if(r == 0)return 1;
    ++l;
    if(s[lf - l] != s[rg + l])return l;
    lf -= l;
    rg += l;
    int cur_l = l;
    l = 0;
    --r;
    // cout << l << ' ' << r << endl;
    // cout << lf << ' ' << rg << '\n';
    while(l < r){
        int m = (l + r + 1)/2;
        if(get_pref(lf - m, lf) * pw[(n - 1) - (rg + m)] % MOD == get_suff(rg, rg + m) * pw[lf - m] % MOD)l = m;
        else r = m - 1;
    }
    //cout << l << endl;
    ++l;
    lf -= l; rg += l;
    return l + cur_l;
}

// consider checking palindrome with hashing and binary search
// adding 1,2,3,4,5 arithmetic sequence with pending/segtree

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s;
    n = s.length();
    pw[0] = 1;
    for(int i = 1; i < n; ++i)pw[i] = pw[i - 1] * 37 % MOD;
    for(int i = 0; i < n; ++i){
        pref[i] = pw[i] * (s[i] - 'a' + 1) % MOD;
        if(i > 0)pref[i] += pref[i - 1];
        pref[i] %= MOD;
    }
    for(int i = n - 1; i >= 0; --i){
        suff[i] = pw[n - 1 - i] * (s[i] - 'a' + 1) % MOD;
        if(i < n - 1)suff[i] += suff[i + 1];
        suff[i] %= MOD;
    }
    ll cnt = 0;
    for(int i = 0; i < n; ++i){
        int l = i, r = i;
        int cur_cnt = find_range(l, r, 0);
        // while(l >= 0 && r < n && s[l] == s[r]){
        //     ++cur_cnt;
        //     --l; ++r;
        // }
        cnt += cur_cnt;
        cur_cnt = i - l - 1;
        diff[l + 1]++;
        diff[i]--;
        if(l + 1 < i){
            diff2[l + 2]++;
            diff2[i]--;
            diff[i] -= cur_cnt - 1;
        }
        diff[i + 1] += cur_cnt;
        diff[r] -= cur_cnt;
        if(i + 1 < r){
            diff2[i + 2]--;
            diff2[r + 1]++;
            diff[r] += cur_cnt;
        }
        // int cur_l = l, cur_r = r;
        // cur_cnt = 0;
        // while(cur_l + 2 < cur_r){
        //     ++cur_l; --cur_r;
        //     ++cur_cnt;
        //     prv[cur_l] += cur_cnt;
        //     prv[cur_r] += cur_cnt;
        // }
        int lf = l, rg = r;
        int cnt_add = get_range(l, r);
        //cout << l << ' ' << r << ' ' << cnt_add << endl;
        // while(l >= 0 && r < n){
        //     --l; ++r;
        //     ++cnt_add;
        //     if(s[l] != s[r])break;
        // }
        //cout << i << " -> " << cnt_add << ' ' << lf << ' ' << rg << endl;
        if(cnt_add && lf >= 0 && rg < n){
            add[lf][s[rg] - 'a'] += cnt_add;
            add[rg][s[lf] - 'a'] += cnt_add;
        }
    }
    for(int i = 1; i < n; ++i){
        int l = i - 1, r = i;
        int cur_cnt = find_range(l, r, 0);
        // while(l >= 0 && r < n && s[l] == s[r]){
        //     ++cur_cnt;
        //     --l; ++r;
        // }
        cnt += cur_cnt;
        cur_cnt = i - 1 - l;
        if(l + 1 < r){
            diff[l + 1]++;
            diff[i]--;
            if(l + 1 < i - 1){
                diff2[l + 2]++;
                diff2[i]--;
                diff[i] -= cur_cnt - 1;
            }
            diff[i] += cur_cnt;
            diff[r] -= cur_cnt;
            if(i < r - 1){
                diff2[i + 1]--;
                diff2[r]++;
                diff[r - 1] += cur_cnt;
            }
        }
        // int cur_l = l, cur_r = r;
        // cur_cnt = 0;
        // while(cur_l + 2 < cur_r){
        //     ++cur_l; --cur_r;
        //     ++cur_cnt;
        //     prv[cur_l] += cur_cnt;
        //     prv[cur_r] += cur_cnt;
        // }
        int lf = l, rg = r;
        int cnt_add = get_range(l, r);
        // while(l >= 0 && r < n){
        //     --l; ++r;
        //     ++cnt_add;
        //     if(s[l] != s[r])break;
        // }
        if(cnt_add && lf >= 0 && rg < n){
            add[lf][s[rg] - 'a'] += cnt_add;
            add[rg][s[lf] - 'a'] += cnt_add;
        }
    }
    // for(int i = 0; i <= n; ++i)cout << diff[i] << ' ';
    // cout << '\n';
    // for(int i = 0; i <= n; ++i)cout << diff2[i] << ' ';
    // cout << '\n';
    for(int i = 0; i < n; ++i){
        if(i > 0)diff2[i] += diff2[i - 1];
        diff[i] += diff2[i];
        if(i > 0)diff[i] += diff[i - 1];
        prv[i] += diff[i];
    }
    //for(int i = 0; i <= n; ++i)cout << prv[i] << ' ';
    //cout << '\n';
    ll max_add = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 26; ++j){
            max_add = max(max_add, add[i][j] - prv[i]);
        }
    }
    //cout << add[5][1] << endl;
    //cout << cnt << '\n';
    cout << cnt + max_add << '\n';
    return 0;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46