oj.uz

Submission #922697

# Submission time Handle Problem Language Result Execution time Memory
922697 2024-02-06T03:12:02 Z vjudge1 Palinilap (COI16_palinilap) C++17
100 / 100
 194 ms 25204 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 3160 KB Output is correct
2 Correct 2 ms 3276 KB Output is correct
3 Correct 2 ms 3160 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 5464 KB Output is correct
3 Correct 8 ms 5208 KB Output is correct
4 Correct 5 ms 5208 KB Output is correct
5 Correct 7 ms 3676 KB Output is correct
6 Correct 8 ms 5468 KB Output is correct
7 Correct 8 ms 4184 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 24664 KB Output is correct
2 Correct 99 ms 25172 KB Output is correct
3 Correct 110 ms 24980 KB Output is correct
4 Correct 179 ms 24860 KB Output is correct
5 Correct 181 ms 25204 KB Output is correct
6 Correct 184 ms 25012 KB Output is correct
7 Correct 179 ms 25004 KB Output is correct
8 Correct 61 ms 4952 KB Output is correct
9 Correct 178 ms 25004 KB Output is correct
10 Correct 185 ms 24912 KB Output is correct
11 Correct 91 ms 25196 KB Output is correct
12 Correct 178 ms 24908 KB Output is correct
13 Correct 172 ms 25000 KB Output is correct
14 Correct 177 ms 24752 KB Output is correct
15 Correct 178 ms 25008 KB Output is correct
16 Correct 108 ms 24916 KB Output is correct
17 Correct 177 ms 25172 KB Output is correct
18 Correct 194 ms 24876 KB Output is correct
19 Correct 176 ms 24912 KB Output is correct