Submission #482952

#	Time	Username	Problem	Language	Result	Execution time	Memory
482952		RGBB	Palindromes (APIO14_palindrome)	C++14	100 / 100	523 ms	42108 KiB

palindrome

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAX=3*1e5;
int n;
string inp;
vector<int>sa;
long long outp;
int IS(int a,vector<int>&arr,vector<int>&s,vector<bool>&sl,vector<int>&lms){
    int i;
    vector<int>num(a),num2(a+1);
    for(i=0;i<s.size();i++){
        num[s[i]]++;
        num2[s[i]+1]++;
    }
    for(i=1;i<a;i++){
        num[i]+=num[i-1];
        num2[i]+=num2[i-1];
    }
    fill(arr.begin(),arr.end(),-1);
    for(i=lms.size()-1;i>=0;i--)arr[--num[s[lms[i]]]]=lms[i];
    for(i=0;i<s.size();i++)if(arr[i]>0&&!sl[arr[i]-1])arr[num2[s[arr[i]-1]]++]=arr[i]-1;
    for(i=0;i<lms.size();i++)num[s[lms[i]]]++;
    for(i=s.size()-1;i>=0;i--)if((arr[i]>0)&&sl[arr[i]-1])arr[--num[s[arr[i]-1]]]=arr[i]-1;
    return 0;
}
vector<int>SAIS(int a,vector<int>&s){
    int i;
    vector<int>arr(s.size()),lms,lms2,s2;
    vector<bool>sl(s.size());
    sl[s.size()-1]=1;
    for(i=s.size()-2;i>=0;i--){
        sl[i]=(s[i]<s[i+1])||((s[i]==s[i+1])&&sl[i+1]);
        if(!sl[i]&&sl[i+1])lms.push_back(i+1);
    }
    reverse(lms.begin(),lms.end());
    IS(a,arr,s,sl,lms);
    lms2.reserve(lms.size()),s2.reserve(lms.size());
    for(i=0;i<s.size();i++)if(arr[i]>0&&sl[arr[i]]&&!sl[arr[i]-1])lms2.push_back(arr[i]);
    int c=0;
    arr[s.size()-1]=c;
    for(i=1;i<lms2.size();i++){
        int x=lms2[i-1];
        int y=lms2[i];
        if(s[x]<s[y])c++;
        else{
            while(true){
                x++;
                y++;
                if(s[x]<s[y]){
                    c++;
                    break;
                }
                else if((sl[x]&&!sl[x-1])||(sl[y]&&!sl[y-1]))break;
            }
        }
        arr[lms2[i]]=c;
    }
    if(c+1<lms2.size()){
        for(i=0;i<lms.size();i++)s2.push_back(arr[lms[i]]);
        vector<int>arr2=SAIS(c+1,s2);
        for(i=0;i<lms.size();i++)lms2[i]=lms[arr2[i]];
    }
    IS(a,arr,s,sl,lms2);
    return arr;
}
vector<int>suffixArray(string&s){
    vector<int>s2(s.begin(),s.end());
    s2.push_back(0);
    s2=SAIS(256,s2);
    s2.erase(s2.begin());
    return s2;
}
vector<int>d1;
void oddManacher(){
    d1=vector<int>(n);
    for(int i=0,l=0,r=-1;i<n;i++){
        int k=(i>r)?1:min(d1[l+r-i],r-i+1);
        while(0<=i-k&&i+k<n&&inp[i-k]==inp[i+k])k++;
        d1[i]=k--;
        if(i+k>r){
            l=i-k;
            r=i+k;
        }
    }
}
vector<int>d2;
void evenManacher(){
    d2=vector<int>(n);
    for(int i=0,l=0,r=-1;i<n;i++){
        int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
        while(0<=i-k-1&&i+k<n&&inp[i-k-1]==inp[i+k])k++;
        d2[i]=k--;
        if(i+k>r){
            l=i-k-1;
            r=i+k;
        }
    }
}
int lzy[1<<20][2];
void delazy(int t,int a,int b,int c){
    if(a==b||lzy[c][t]==-1)return;
    lzy[2*c+1][t]=lzy[c][t];
    lzy[2*c+2][t]=lzy[c][t];
    lzy[c][t]=-1;
}
int querySeg(int t,int a,int b,int p,int c){
    if(a>p||b<p)return -1;
    delazy(t,a,b,c);
    if(a==b)return lzy[c][t];
    return max(querySeg(t,a,(a+b)/2,p,2*c+1),querySeg(t,(a+b)/2+1,b,p,2*c+2));
}
void updateSeg(int t,int a,int b,int be,int en,int c,int v){
    if(a>en||b<be)return;
    delazy(t,a,b,c);
    if(a>=be&&b<=en){
        lzy[c][t]=v;
        return;
    }
    updateSeg(t,a,(a+b)/2,be,en,2*c+1,v);
    updateSeg(t,(a+b)/2+1,b,be,en,2*c+2,v);
}
int bit[MAX+1];
int queryBit(int be,int en){
    int ret=0;
    for(en++;en>0;en-=en&-en)ret+=bit[en];
    for(;be>0;be-=be&-be)ret-=bit[be];
    return ret;
}
void updateBit(int p,int v){
    for(p++;p<=n;p+=p&-p)bit[p]+=v;
}
set<int>cnt[MAX];
void deleteRange(int be,int en,int p){
    while(cnt[p].lower_bound(be)!=cnt[p].end()){
        int cur=*cnt[p].lower_bound(be);
        if(cur>en)break;
        updateBit(cur,-1);
        cnt[p].erase(cnt[p].find(cur));
    }
}
void solve(int pty,vector<int>&d){
    memset(lzy,-1,sizeof(lzy));
    memset(bit,0,sizeof(bit));
    for(int i=0;i<n;i++)if(d[sa[i]]!=0)updateBit(i,1);
    for(int i=0;i<n;i++)cnt[i].clear();
    for(int i=0;i<n;i++)cnt[d[sa[i]]].insert(i);
    for(int i=0;i<n;i++){
        int cap=querySeg(0,0,n-1,i,0);
        int l=i;
        int r=querySeg(1,0,n-1,i,0);
        if(r==-1)r=n-1;
        int m=(l+r)/2;
        for(int j=cap+1;j<d[sa[i]];j++){
            while(r-l>1){
                if(inp[sa[i]+j]==(sa[m]+j<n?inp[sa[m]+j]:'$'))l=m;
                else r=m;
                m=(l+r)/2;
            }
            if(inp[sa[i]+j]==(sa[r]+j<n?inp[sa[r]+j]:'$'))m=r;
            else m=l;
            outp=max(outp,(long long)(2*j-pty+2)*queryBit(i,m));
            deleteRange(i,m,j+1);
            updateSeg(0,0,n-1,i,m,0,j);
            updateSeg(1,0,n-1,i,m,0,m);
            r=m;
            l=i;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>inp;
    n=inp.length();
    sa=suffixArray(inp);
    oddManacher();
    evenManacher();
    solve(1,d1);
    solve(0,d2);
    cout<<outp<<"\n";
}

Compilation message (stderr)

palindrome.cpp: In function 'int IS(int, std::vector<int>&, std::vector<int>&, std::vector<bool>&, std::vector<int>&)':
palindrome.cpp:12:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(i=0;i<s.size();i++){
      |             ~^~~~~~~~~
palindrome.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(i=0;i<s.size();i++)if(arr[i]>0&&!sl[arr[i]-1])arr[num2[s[arr[i]-1]]++]=arr[i]-1;
      |             ~^~~~~~~~~
palindrome.cpp:23:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(i=0;i<lms.size();i++)num[s[lms[i]]]++;
      |             ~^~~~~~~~~~~
palindrome.cpp: In function 'std::vector<int> SAIS(int, std::vector<int>&)':
palindrome.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(i=0;i<s.size();i++)if(arr[i]>0&&sl[arr[i]]&&!sl[arr[i]-1])lms2.push_back(arr[i]);
      |             ~^~~~~~~~~
palindrome.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(i=1;i<lms2.size();i++){
      |             ~^~~~~~~~~~~~
palindrome.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if(c+1<lms2.size()){
      |        ~~~^~~~~~~~~~~~
palindrome.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(i=0;i<lms.size();i++)s2.push_back(arr[lms[i]]);
      |                 ~^~~~~~~~~~~
palindrome.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(i=0;i<lms.size();i++)lms2[i]=lms[arr2[i]];
      |                 ~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27