Submission #713062

#	Time	Username	Problem	Language	Result	Execution time	Memory
713062		bin9638	Palindromes (APIO14_palindrome)	C++17	100 / 100	908 ms	67736 KiB

palindrome

#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 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27