Submission #267007

#TimeUsernameProblemLanguageResultExecution timeMemory
267007uacoder123Palindromes (APIO14_palindrome)C++14
0 / 100
525 ms76160 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) lli(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; string s; lli n,co=0; vi sa(300001),t1(300001),t2(300001),cnt(300001),c(300001); lli r[300001],lcp[300001],lo[300001],sp[300001][20],d1[300001],d2[300001],le=0,ri=-1,ans=0; lli cot(lli l,lli ri) { lli left=r[l],rig=n-1,ans=l,ans1=0; while(left<=rig) { lli m1=(left+rig)/2,m; m=m1-1; lli ch=(m1==r[l])?(ri-l+1):(min(sp[r[l]][lo[m-r[l]+1]],sp[m-lo[m-r[l]+1]][lo[m-r[l]+1]])); if(ch>=(ri-l+1)) { left=m1+1; ans=m1; } else rig=m1-1; } ans1+=ans-r[l]+1; left=0; rig=r[l]; ans=r[l]; while(left<=rig) { lli m1=(left+rig)/2,m; m=m1-1; lli ch=(m==r[l])?ri-l+1:min(sp[m][lo[r[l]-m+1]],sp[r[l]-lo[r[l]-m+1]][lo[r[l]-m+1]]); if(ch>=(ri-l+1)) { rig=m1-1; ans=m1; } else left=m1+1; } ans1+=r[l]-ans; return ans1; } void cal() { pair<char,lli> s1[n]; for(lli i=0;i<n;++i) s1[i]=mp(s[i],i); sort(s1,s1+n); c[0]=0; co++; sa[0]=s1[0].S; for(lli i=1;i<n;++i) { if(s1[i].F!=s1[i-1].F) co++; c[s1[i].S]=co-1; sa[i]=s1[i].S; } for(lli k=1;(1<<(k-1))<n;++k) { for(lli i=0;i<n;++i) { cnt[i]=0; t1[i]=(sa[i]-(1<<(k-1))+n)%n; } for(lli i=0;i<n;++i) cnt[c[t1[i]]]++; for(lli i=1;i<co;++i) cnt[i]+=cnt[i-1]; for(lli i=0;i<=n-1;++i) sa[--cnt[c[t1[i]]]]=t1[i]; t2[sa[0]]=0; co=1; for(lli i=1;i<n;++i) { ii cur=mp(c[sa[i]],c[(sa[i]+(1<<k-1))]); ii prev=mp(c[sa[i-1]],c[(sa[i-1]+(1<<k-1))%n]); if(cur!=prev) co++; t2[sa[i]]=co-1; } swap(t2,c); } sa.erase(sa.begin()); n--; for(lli i=0;i<n;++i) r[sa[i]]=i; } void cal1() { lli k=0; for(lli i=0;i<n;++i) { if(r[i]==n-1) { k=0; continue; } lli j=sa[r[i]+1]; while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++; lcp[r[i]]=k; if(k) k--; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>s; n=s.size(); if(n==1) { cout<<1<<endl; exit(0); } s+="#"; n++; cal(); cal1(); for(lli i=2;i<=n;++i) lo[i]=lo[i/2]+1; for(lli i=0;i<20;++i) { for(lli j=0;j<n;++j) { if(i==0) sp[j][i]=lcp[j]; else if(j+(1LL<<i)<=n) { sp[j][i]=min(sp[j][i-1],sp[j+(1<<(i-1))][i-1]); } } } for(lli i=0;i<n;++i) { lli k=(i>ri)?1:min(ri-i+1,d1[le+ri-i]); ans=max(ans,cot(i,i)); while(i+k<n&&i-k>=0&&s[i+k]==s[i-k]) { ans=max(cot(i-k,i+k)*(2*k+1),ans); k++; } d1[i]=k; if(d1[i]+i-1>ri) { ri=d1[i]+i-1; le=i-d1[i]+1; } } le=0; ri=-1; for(lli i=0;i<n;++i) { lli k=(i>ri)?0:min(ri-i+1,d1[le+ri-i]); while(i+k<n&&i-k-1>=0&&s[i+k]==s[i-k-1]) { ans=max(cot(i-k-1,i+k)*(2*k+2),ans); k++; } d2[i]=k; if(d2[i]+i-1>ri) { ri=d2[i]+i-1; le=i-d2[i]; } } cout<<ans<<endl; return(0); }

Compilation message (stderr)

palindrome.cpp: In function 'void cal()':
palindrome.cpp:90:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   90 |       ii cur=mp(c[sa[i]],c[(sa[i]+(1<<k-1))]);
      |                                       ~^~
palindrome.cpp:9:29: note: in definition of macro 'mp'
    9 | #define mp(i,a) make_pair(i,a)
      |                             ^
palindrome.cpp:91:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |       ii prev=mp(c[sa[i-1]],c[(sa[i-1]+(1<<k-1))%n]);
      |                                            ~^~
palindrome.cpp:9:29: note: in definition of macro 'mp'
    9 | #define mp(i,a) make_pair(i,a)
      |                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...