oj.uz

Submission #137732

# Submission time Handle Problem Language Result Execution time Memory
137732 2019-07-28T09:15:17 Z futurer Palinilap (COI16_palinilap) C++14
54 / 100
 530 ms 30468 KB 
// 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 = 23;
    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>=0;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]; 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>=0;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]; 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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5112 KB Output is correct
2 Correct 14 ms 5112 KB Output is correct
3 Correct 14 ms 5112 KB Output is correct
4 Correct 16 ms 5112 KB Output is correct
5 Correct 20 ms 5112 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6392 KB Output is correct
2 Correct 29 ms 6264 KB Output is correct
3 Correct 32 ms 6520 KB Output is correct
4 Correct 23 ms 5880 KB Output is correct
5 Correct 28 ms 6136 KB Output is correct
6 Correct 31 ms 6392 KB Output is correct
7 Correct 30 ms 6364 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 30360 KB Output is correct
2 Incorrect 430 ms 30468 KB Output isn't correct
3 Halted 0 ms 0 KB -