oj.uz

Submission #955191

# Submission time Handle Problem Language Result Execution time Memory
955191 2024-03-29T15:51:13 Z jhinezeal123 Palinilap (COI16_palinilap) C++14
100 / 100
 136 ms 95844 KB 
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
using namespace std;
const double eps = 0.0000001;
const int mod1 = 998244353,mod2 = 1e9+7;
const int N = 500005;
const int MATRIX_SIZE = 64;
int n,ans,ansT,them[N][30],base1=31,base2=575,sum1,sum2,sl1,sl2;
ii Hash1[N],Hash2[N],P[N];
vector <int> add1[N],sub1[N],add2[N],sub2[N];
string s;
ii get1(int l,int r){
    return {(Hash1[r].fi-Hash1[l-1].fi*P[r-l+1].fi+mod1*mod1)%mod1,(Hash1[r].se-Hash1[l-1].se*P[r-l+1].se+mod2*mod2)%mod2};
}
ii get2(int l,int r){
    return {(Hash2[l].fi-Hash2[r+1].fi*P[r-l+1].fi+mod1*mod1)%mod1,(Hash2[l].se-Hash2[r+1].se*P[r-l+1].se+mod2*mod2)%mod2};
}
void even(int pos){
    int res=0,l=1,r=min(pos,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid+1,pos)==get2(pos+1,pos+mid)){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 1 "<<res<<endl;
    add2[pos-res+1].push_back(pos-res+1);
    sub2[pos+1].push_back(pos-res+1);
    add1[pos+1].push_back(pos+res);
    sub1[pos+res+1].push_back(pos+res);
    ansT+=res;
    if (res==min(pos,n-pos)) return;
    int tam=res+1;
    l=res+2;
    r=min(pos,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid+1,pos-res-1)==get2(pos+res+2,pos+mid)){
            tam=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 1 "<<tam<<endl;
    // cout<<pos-res<<' '<<s[pos+res+1]-'a'+1<<' '<<pos+res+1<<' '<<s[pos-res]-'a'+1<<endl;
    tam-=res;
    them[pos-res][s[pos+res+1]-'a'+1]+=tam;
    them[pos+res+1][s[pos-res]-'a'+1]+=tam;
}
void odd(int pos){
    int res=0,l=1,r=min(pos-1,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid,pos-1)==get2(pos+1,pos+mid)){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 2 "<<res<<endl;
    ansT+=res+1;
    add2[pos-res].push_back(pos-res);
    sub2[pos].push_back(pos-res);
    add1[pos+1].push_back(pos+res);
    sub1[pos+res+1].push_back(pos+res);
    if (res==min(pos-1,n-pos)) return;
    int tam=res+1;
    l=res+2;
    r=min(pos-1,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid,pos-res-2)==get2(pos+res+2,pos+mid)){
            tam=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 2 "<<tam<<endl;
    // cout<<pos-res-1<<' '<<s[pos+res+1]-'a'+1<<' '<<pos+res+1<<' '<<s[pos-res-1]-'a'+1<<endl;
    tam-=res;
    them[pos-res-1][s[pos+res+1]-'a'+1]+=tam;
    them[pos+res+1][s[pos-res-1]-'a'+1]+=tam;
}
void FindPalind(){
    for (int i=1;i<=n;++i){
        even(i);
        odd(i);
    }
}
void Dp(){
    for (int i=1,tru,cong;i<=n;++i){
        for (auto it:add1[i]){
            ++sl1;
            sum1+=it;
        }
        for (auto it:add2[i]){
            ++sl2;
            sum2+=it;
        }
        for (auto it:sub1[i]){
            --sl1;
            sum1-=it;
        }
        for (auto it:sub2[i]){
            --sl2;
            sum2-=it;
        }
        tru=sum1-sl1*(i-1)+sl2*(i+1)-sum2;
        for (int j=1;j<=26;++j){
            cong=them[i][j];
            ans=max(ans,ansT-tru+cong);
            // if (ansT-tru+cong==8) cout<<tru<<' '<<cong<<endl;
        }
    }
}
void solve(){
    cin>>s;
    n=s.size();
    s=' '+s+'$';
    P[0]={1,1};
    for (int i=1;i<=n;++i){
        P[i]={P[i-1].fi*base1%mod1,P[i-1].se*base2%mod2};
        Hash1[i]={(Hash1[i-1].fi*base1+s[i]-'a'+1)%mod1,(Hash1[i-1].se*base2+s[i]-'a'+1)%mod2};
    }
    for (int i=n;i>=1;--i){
        Hash2[i]={(Hash2[i+1].fi*base1+s[i]-'a'+1)%mod1,(Hash2[i+1].se*base2+s[i]-'a'+1)%mod2};
    }
    FindPalind();
    ans=ansT;
    // cout<<ansT<<endl;
    Dp();
    cout<<ans;
}
main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // init();
    solve();
    // cout<<clock()/1000.0;
}

Compilation message

palinilap.cpp:143:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  143 | main() {
      | ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49748 KB Output is correct
2 Correct 13 ms 49752 KB Output is correct
3 Correct 12 ms 49904 KB Output is correct
4 Correct 13 ms 49756 KB Output is correct
5 Correct 12 ms 49900 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 50780 KB Output is correct
2 Correct 17 ms 50776 KB Output is correct
3 Correct 15 ms 50520 KB Output is correct
4 Correct 14 ms 50268 KB Output is correct
5 Correct 15 ms 50468 KB Output is correct
6 Correct 20 ms 50616 KB Output is correct
7 Correct 16 ms 50712 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 94112 KB Output is correct
2 Correct 83 ms 94816 KB Output is correct
3 Correct 95 ms 94920 KB Output is correct
4 Correct 117 ms 94196 KB Output is correct
5 Correct 115 ms 94196 KB Output is correct
6 Correct 117 ms 94064 KB Output is correct
7 Correct 117 ms 94244 KB Output is correct
8 Correct 72 ms 70160 KB Output is correct
9 Correct 117 ms 94104 KB Output is correct
10 Correct 119 ms 93984 KB Output is correct
11 Correct 84 ms 94732 KB Output is correct
12 Correct 131 ms 95844 KB Output is correct
13 Correct 121 ms 94188 KB Output is correct
14 Correct 118 ms 93940 KB Output is correct
15 Correct 115 ms 93964 KB Output is correct
16 Correct 92 ms 94828 KB Output is correct
17 Correct 102 ms 93284 KB Output is correct
18 Correct 114 ms 93428 KB Output is correct
19 Correct 101 ms 93452 KB Output is correct