oj.uz

Submission #713062

# Submission time Handle Problem Language Result Execution time Memory
713062 2023-03-21T02:46:03 Z bin9638 Palindromes (APIO14_palindrome) C++17
100 / 100
 908 ms 67736 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 300010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double

int n;
string s;
ll ans=0;

/*struct BIT
{
    int bit[N]={};

    void init()
    {
        memset(bit,0,sizeof(bit));
    }

    void update(int u,int val)
    {
        for(;u<=n;u+=u&(-u))
            bit[u]+=val;
    }

    int get(int u)
    {
        int res=0;
        for(;u>0;u-=u&(-u))
            res+=bit[u];
        return res;
    }
}BIT;*/

struct DoubleHash
{
    vector<ll> H1, H2, p1, p2;
    ll base1 = 311, base2 = 313, mod1 = 1e9 + 8277, mod2 = 1e9 + 9277;
    void init(string s, int n)
    {
        p1.resize(n + 1, 1), p2.resize(n + 1, 1), H1.resize(n + 1, 0), H2.resize(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            p1[i] = p1[i - 1] * base1 % mod1;
            p2[i] = p2[i - 1] * base2 % mod2;
            H1[i] = (H1[i - 1] * base1 + s[i]-'A'+1) % mod1;
            H2[i] = (H2[i - 1] * base2 + s[i]-'A'+1) % mod2;
        }
    }
    ll getHash(int u, int v)
    {
        ll t1 = (H1[v] - H1[u - 1] * p1[v - u + 1] + mod1 * mod1) % mod1;
        ll t2 = (H2[v] - H2[u - 1] * p2[v - u + 1] + mod2 * mod2) % mod2;
        return t1 * 1000000000 + t2;
    }
}xuoi,nguoc;

bool check_palin(int l,int r)
{
    return (xuoi.getHash(l,r)==nguoc.getHash(n-r+1,n-l+1));
}
struct SA
{
    int sa[N]={},pos[N]={},lcp[N]={},cnt[N]={},tmp[N]={};
bool SS(int u,int v,int k)
{
    if(pos[u]!=pos[v])
        return pos[u]<pos[v];
    if(u+k<=n&&v+k<=n)
        return pos[u+k]<pos[v+k];
    return(u>v);
}

void countsort(int k)
{
    fill(cnt,cnt+1+max(256,n),0);
    for(int i=1;i<=n;i++)
        cnt[(i+k<=n ? pos[i+k] : 0)]++;
    for(int i=1;i<=max(256,n);i++)
        cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)
        tmp[cnt[(sa[i]+k<=n ? pos[sa[i]+k] : 0)]--]=sa[i];
    for(int i=1;i<=n;i++)
        sa[i]=tmp[i];
}

void make_SA()
{
    for(int i=1;i<=n;i++)
    {
        sa[i]=i;
        pos[i]=s[i];
    }
    for(int k=1;k<=n;k<<=1)
    {
        countsort(k);
        countsort(0);
        tmp[sa[1]]=1;
        for(int i=2;i<=n;i++)
            tmp[sa[i]]=tmp[sa[i-1]]+SS(sa[i-1],sa[i],k);
        for(int i=1;i<=n;i++)
            pos[i]=tmp[i];
    }
}

void make_lcp()
{
    for(int i=1;i<=n;i++)
        pos[sa[i]]=i;
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(pos[i]==n)
        {
            lcp[pos[i]]=0;
            continue;
        }
        int j=sa[pos[i]+1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])
            k++;
        lcp[pos[i]]=k;
        k-=(k>0);
    }
}

vector<int>gop[N];

void build()
{
    for(int i=1;i<n;i++)
        gop[lcp[i]].pb(i);
}
}SA;

struct DSU
{
    int dem=0,lab[N]={},sz[N]={};

    void init()
    {
        dem=0;
        memset(lab,-1,sizeof(lab));
        memset(sz,0,sizeof(sz));
    }

    int root(int u)
    {
        if(lab[u]<0)
            return u;
        return(lab[u]=root(lab[u]));
    }

    void update(int u,int v)
    {
        if((u=root(u))==(v=root(v)))
            return;
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
        sz[u]+=sz[v];
        dem=max(dem,sz[u]);
    }

    void them(int u)
    {
        u=root(u);
        dem=max(dem,++sz[u]);
    }
}DSU;

struct le
{
    vector<int>lis[N];

    void solve()
    {
        //BIT.init();
        DSU.init();
        for(int i=1;i<=n;i++)
        {
            int val=0,l=1,r=min(i,n-i+1);
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(check_palin(i-mid+1,i+mid-1))
                {
                    val=mid;
                    l=mid+1;
                }else
                    r=mid-1;
            }
            lis[val].pb(SA.pos[i]);
        }
        for(int length=n;length>=1;length--)
        {
             for(auto u:lis[length])
                DSU.them(u);
             for(auto u:SA.gop[length])
                DSU.update(u,u+1);
             ans=max(ans,1ll*DSU.dem*(length*2-1));
        }
    }
}le;

struct chan
{
    vector<int>lis[N];

    void solve()
    {
        //BIT.init();
        DSU.init();
        for(int i=1;i<=n;i++)
        {
            int val=0,l=1,r=min(i-1,n-i+1);
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(check_palin(i-mid,i+mid-1))
                {
                    val=mid;
                    l=mid+1;
                }else
                    r=mid-1;
            }
            lis[val].pb(SA.pos[i]);
        }
        for(int length=n;length>=1;length--)
        {
             for(auto u:lis[length])
                DSU.them(u);
             for(auto u:SA.gop[length])
                DSU.update(u,u+1);
             ans=max(ans,1ll*DSU.dem*(length*2));
        }
    }
}chan;

int main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s;
    n=s.size();
    s=" "+s;
    for(int i=1;i*2<=n;i++)
        swap(s[i],s[n-i+1]);
    nguoc.init(s,n);
    for(int i=1;i*2<=n;i++)
        swap(s[i],s[n-i+1]);
    xuoi.init(s,n);
    SA.make_SA();
    SA.make_lcp();
    SA.build();
    //cout<<s<<endl;
   // for(int i=1;i<=n;i++)cout<<SA.sa[i]<<" "<<SA.lcp[i]<<endl;
    le.solve();
    chan.solve();
    cout<<ans;
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29652 KB Output is correct
2 Correct 17 ms 29660 KB Output is correct
3 Correct 14 ms 29652 KB Output is correct
4 Correct 14 ms 29652 KB Output is correct
5 Correct 18 ms 29644 KB Output is correct
6 Correct 17 ms 29556 KB Output is correct
7 Correct 14 ms 29640 KB Output is correct
8 Correct 14 ms 29652 KB Output is correct
9 Correct 18 ms 29624 KB Output is correct
10 Correct 14 ms 29644 KB Output is correct
11 Correct 17 ms 29608 KB Output is correct
12 Correct 14 ms 29652 KB Output is correct
13 Correct 15 ms 29644 KB Output is correct
14 Correct 15 ms 29612 KB Output is correct
15 Correct 16 ms 29636 KB Output is correct
16 Correct 14 ms 29592 KB Output is correct
17 Correct 14 ms 29652 KB Output is correct
18 Correct 17 ms 29644 KB Output is correct
19 Correct 16 ms 29612 KB Output is correct
20 Correct 14 ms 29640 KB Output is correct
21 Correct 15 ms 29652 KB Output is correct
22 Correct 15 ms 29652 KB Output is correct
23 Correct 15 ms 29620 KB Output is correct
24 Correct 15 ms 29644 KB Output is correct
25 Correct 16 ms 29652 KB Output is correct
26 Correct 15 ms 29656 KB Output is correct
27 Correct 16 ms 29676 KB Output is correct
28 Correct 15 ms 29640 KB Output is correct
29 Correct 15 ms 29640 KB Output is correct
30 Correct 14 ms 29652 KB Output is correct
31 Correct 14 ms 29652 KB Output is correct
32 Correct 14 ms 29644 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29768 KB Output is correct
2 Correct 15 ms 29776 KB Output is correct
3 Correct 15 ms 29736 KB Output is correct
4 Correct 19 ms 29728 KB Output is correct
5 Correct 16 ms 29780 KB Output is correct
6 Correct 17 ms 29780 KB Output is correct
7 Correct 15 ms 29652 KB Output is correct
8 Correct 16 ms 29756 KB Output is correct
9 Correct 16 ms 29752 KB Output is correct
10 Correct 15 ms 29652 KB Output is correct
11 Correct 15 ms 29656 KB Output is correct
12 Correct 16 ms 29652 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30892 KB Output is correct
2 Correct 28 ms 30732 KB Output is correct
3 Correct 29 ms 30924 KB Output is correct
4 Correct 30 ms 30748 KB Output is correct
5 Correct 29 ms 30612 KB Output is correct
6 Correct 30 ms 30504 KB Output is correct
7 Correct 28 ms 30548 KB Output is correct
8 Correct 28 ms 30548 KB Output is correct
9 Correct 29 ms 30548 KB Output is correct
10 Correct 29 ms 30540 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 41480 KB Output is correct
2 Correct 190 ms 39424 KB Output is correct
3 Correct 201 ms 42432 KB Output is correct
4 Correct 198 ms 40172 KB Output is correct
5 Correct 204 ms 38424 KB Output is correct
6 Correct 198 ms 38668 KB Output is correct
7 Correct 196 ms 38552 KB Output is correct
8 Correct 237 ms 37860 KB Output is correct
9 Correct 221 ms 38512 KB Output is correct
10 Correct 220 ms 38732 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 65700 KB Output is correct
2 Correct 609 ms 56824 KB Output is correct
3 Correct 645 ms 67736 KB Output is correct
4 Correct 623 ms 57544 KB Output is correct
5 Correct 732 ms 57044 KB Output is correct
6 Correct 623 ms 55964 KB Output is correct
7 Correct 628 ms 55392 KB Output is correct
8 Correct 796 ms 54868 KB Output is correct
9 Correct 908 ms 54748 KB Output is correct
10 Correct 754 ms 56532 KB Output is correct
11 Correct 579 ms 62996 KB Output is correct
12 Correct 804 ms 55724 KB Output is correct