oj.uz

Submission #922717

# Submission time Handle Problem Language Result Execution time Memory
922717 2024-02-06T03:58:40 Z boyliguanhan Palinilap (COI16_palinilap) C++17
100 / 100
 187 ms 25176 KB 
#include<bits/stdc++.h>
#define N 100100
using namespace std;
#define X (1<<j)
long long ans,nc,cont[N][26],bad[2][N],n,hl[N],hr[N],pw[N]{1},A=31,B=1e9+7;
int Hl(int l, int r) {return(hl[r]-hl[l]*pw[r-l]%B+B)%B;}
int Hr(int l, int r) {return(hr[l]-hr[r]*pw[r-l]%B+B)%B;}
int main() {
    for(int i=1;i<N;i++) pw[i]=pw[i-1]*A%B;
    string str;
    char c=getchar();
    while(c>'A')str+=c,c=getchar();
    n=str.size();
    for(int i=1;i<=n;i++)
        hl[i]=hr[i]=str[i-1]-'a'+1;
    for(int i=1;i<n;i++)
        hl[i+1]+=(hl[i]*A)%B,
        hr[n-i]+=(hr[n-i+1]*A)%B;
    for(int i=1;i<n;i++){
        int p1=i,p2=i+1,p3,p4;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        bad[1][p2-1]++,bad[1][i]+=i-p2,bad[1][i-1]+=p2-i-1;
        nc+=i-p1;
        bad[0][p1+1]++;bad[0][i+1]+=p1-i-1;bad[0][i+2]+=i-p1;
        p3=p1--,p4=p2++;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        if(p3&&p4<=n)cont[p3][str[p4-1]-'a']+=p3-p1,
            cont[p4][str[p3-1]-'a']+=p3-p1;
    }
    for(int i=1;i<=n;i++){
        int p1=i,p2=i,p3,p4;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        bad[1][p2-1]++,bad[1][i]+=p1-i,bad[1][i-1]+=i-p1-1;
        nc+=i-p1;
        bad[0][p1+1]++,bad[0][i]+=p1-i;bad[0][i+1]+=i-p1-1;
        p3=p1--,p4=p2++;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        if(p3&&p4<=n)cont[p3][str[p4-1]-'a']+=p3-p1,
            cont[p4][str[p3-1]-'a']+=p3-p1;
    }
    for(int i=2;i<=n;i++)
        bad[0][i]+=bad[0][i-1];
    for(int i=2;i<=n;i++)
        bad[0][i]+=bad[0][i-1];
    for(int i=n;--i;)
        bad[1][i]+=bad[1][i+1];
    for(int i=n;--i;)
        bad[1][i]+=bad[1][i+1];
    for(int i=1;i<=n;i++)for(auto j:cont[i])
        ans=max(ans,j-bad[0][i]-bad[1][i]);
    cout<<ans+nc;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 2 ms 3276 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 8 ms 5212 KB Output is correct
4 Correct 5 ms 5212 KB Output is correct
5 Correct 7 ms 5328 KB Output is correct
6 Correct 8 ms 5212 KB Output is correct
7 Correct 8 ms 5460 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 24752 KB Output is correct
2 Correct 93 ms 25176 KB Output is correct
3 Correct 106 ms 24764 KB Output is correct
4 Correct 175 ms 24996 KB Output is correct
5 Correct 187 ms 25172 KB Output is correct
6 Correct 176 ms 24912 KB Output is correct
7 Correct 178 ms 24912 KB Output is correct
8 Correct 61 ms 4952 KB Output is correct
9 Correct 176 ms 24912 KB Output is correct
10 Correct 175 ms 25012 KB Output is correct
11 Correct 88 ms 24772 KB Output is correct
12 Correct 174 ms 24916 KB Output is correct
13 Correct 167 ms 24916 KB Output is correct
14 Correct 180 ms 24912 KB Output is correct
15 Correct 175 ms 24916 KB Output is correct
16 Correct 107 ms 25004 KB Output is correct
17 Correct 174 ms 25004 KB Output is correct
18 Correct 176 ms 25004 KB Output is correct
19 Correct 184 ms 25000 KB Output is correct