Submission #137825

#	Time	Username	Problem	Language	Result	Execution time	Memory
137825		futurer	Palinilap (COI16_palinilap)	C++14	54 / 100	536 ms	30424 KiB

palinilap

// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5, L = 26;
#define MID(l, r) ((l+r)>>1)
int LNF[N], LNZ[N],  n;
long long dp[N][L], PS[N], T[N], rt, rtt;
char S[N];
void ah() { cerr << "!!!\n"; }
struct HS1{
    int mod = 1e9+7, bs = 9973;
    int zrb(int a, int b) { return(1LL*a*b%mod); }
    int  jm(int a, int b) { int tmp=(a+b)%mod; while(tmp<0) tmp+=mod; return(tmp); }
    int  pw(int a, int b) { int rt=1; for(;b;b>>=1){ if(b&1) rt=zrb(rt, a); a=zrb(a, a); } return(rt); }
    int PS[N], RV[N], P[N], INV[N];
    inline void ini(){
        n = strlen(S);
        P[0] = 1; for(int i=1;i<N;i++) P[i] = zrb(P[i-1], bs);
        INV[N-1] = pw(P[N-1], mod-2); for(int i=N-2;~i;i--) INV[i] = zrb(INV[i+1], bs);
        PS[0] = S[0]; for(int i=1;i<n;i++) PS[i] = jm(PS[i-1], zrb(S[i], P[i]));
        RV[n-1] = S[n-1]; for(int i=n-2;~i;i--) RV[i]=jm(RV[i+1], zrb(S[i], P[n-i-1]));
    }
    int get(int l, int r){
        int rt = PS[r]; if(l) rt=jm(rt, -PS[l-1]);
        return(zrb(rt, INV[l]));
    }
    int getrv(int l, int r){
        int rt = RV[l]; if(r+1<n) rt=jm(rt, -RV[r+1]);
        return(zrb(rt, INV[n-r-1]));
    }
} f1;
struct HS2{
    int mod = 1e9+9, bs = 701;
    int zrb(int a, int b) { return(1LL*a*b%mod); }
    int  jm(int a, int b) { int tmp=(a+b)%mod; while(tmp<0) tmp+=mod; return(tmp); }
    int  pw(int a, int b) { int rt=1; for(;b;b>>=1){ if(b&1) rt=zrb(rt, a); a=zrb(a, a); } return(rt); }
    int PS[N], RV[N], P[N], INV[N];
    inline void ini(){
        n=strlen(S);
        P[0] = 1; for(int i=1;i<N;i++) P[i] = zrb(P[i-1], bs);
        INV[N-1] = pw(P[N-1], mod-2); for(int i=N-2;~i;i--) INV[i] = zrb(INV[i+1], bs);
        PS[0] = S[0]; for(int i=1;i<n;i++) PS[i] = jm(PS[i-1], zrb(S[i], P[i]));
        RV[n-1] = S[n-1]; for(int i=n-2;~i;i--) RV[i]=jm(RV[i+1], zrb(S[i], P[n-i-1]));
    }
    int get(int l, int r){
        int rt = PS[r]; if(l) rt=jm(rt, -PS[l-1]);
        return(zrb(rt, INV[l]));
    }
    int getrv(int l, int r){
        int rt = RV[l]; if(r+1<n) rt=jm(rt, -RV[r+1]);
        return(zrb(rt, INV[n-r-1]));
    }
} f2;
bool C(int l, int r) { return(f1.get(l, r)==f1.getrv(l, r)&&f2.get(l, r)==f2.getrv(l, r)); }
int32_t main(){
    scanf("%s", S);
    f1.ini(); f2.ini();
    for(int i=0;i<n;i++){
        int l=0, r=n;
        while(r-l>1){
            int mid = MID(l, r);
            int a=i-mid, b=i+mid;
            if(a<0||b>=n) { r=mid; continue; }
            if(C(a, b)) l=mid;
            else r=mid;
        }
        LNF[i]=l;
        rt+=l+1;
        int ll=i-l, rr=i+l;
        ll--; rr++;
        l=0, r=n;
        while(r-l>1){
            int mid = MID(l, r);
            int a=ll-mid, b=rr+mid;
            if(a<0||b>=n) { r=mid; continue; }
            if(f1.get(a, ll-1)==f1.getrv(rr+1, b)&&f2.get(a, ll-1)==f2.getrv(rr+1, b)) l=mid;
            else r=mid;
        }
        dp[ll][S[rr]-'a']+=l+1;
        dp[rr][S[ll]-'a']+=l+1;
    }
    for(int i=0;i<n-1;i++){
        int l=-1, r=n;
        while(r-l>1){
            int mid = MID(l, r);
            int a=i-mid, b=i+mid+1;
            if(a<0||b>=n) { r=mid; continue; }
            if(C(a, b)) l=mid;
            else r=mid;
        }
        LNZ[i]=l;
        rt+=l+1;
        int ll=i-l, rr=i+l+1;
        ll--; rr++;
        l=0, r=n;
        while(r-l>1){
            int mid = MID(l, r);
            int a=ll-mid, b=rr+mid;
            if(a<0||b>=n) { r=mid; continue; }
            if(f1.get(a, ll-1)==f1.getrv(rr+1, b)&&f2.get(a, ll-1)==f2.getrv(rr+1, b)) l=mid;
            else r=mid;
        }
        dp[ll][S[rr]-'a']+=l+1;
        dp[rr][S[ll]-'a']+=l+1;
    }
    for(int i=0;i<n;i++){
        int l=i-LNF[i], r=i+LNF[i];
        if(l==r) continue; 
        PS[l]-=l; PS[i]+=l;
        PS[i+1]+=r; PS[r+1]-=r;
        PS[l]++; PS[i]--;
        PS[i+1]++; PS[r+1]--;
        T[l]++; T[i]--; T[i+1]--; T[r+1]++;
    }
    for(int i=0;i<n-1;i++) if(~LNZ[i]){
        int l=i-LNZ[i], r=i+LNZ[i]+1;
        PS[l]-=l; PS[i+1]+=l;
        PS[i+1]+=r; PS[r+1]-=r;
        PS[l]++; PS[i+1]--;
        PS[i+1]++; PS[r+1]--;
        T[l]++; T[i+1]--; T[i+1]--; T[r+1]++;
    }
    rtt=rt;
    for(int i=1;i<N;i++) PS[i]+=PS[i-1];
    for(int i=1;i<N;i++) T[i]+=T[i-1];
    for(int i=0;i<n;i++) for(int j=0;j<L;j++){
        rtt=max(rtt, rt+dp[i][j]-(PS[i]+1LL*T[i]*i));
    }
    printf("%lld", rtt);
}

Compilation message (stderr)

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

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