Submission #335699

#TimeUsernameProblemLanguageResultExecution timeMemory
335699alishahali1382회문 (APIO14_palindrome)C++14
100 / 100
659 ms63476 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O2") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize("no-stack-protector,fast-math") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; const ld eps=1e-7; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=1000000007; const int MAXN=300010, LOG=19; int n, m, k, u, v, x, y, t, a, b; ll ans; int Rank[LOG][MAXN<<1], P[MAXN<<1], P2[MAXN<<1], cnt[MAXN<<1]; int lcp[MAXN], L[MAXN], R[MAXN]; int seg[MAXN<<2]; int shit[MAXN<<1]; int f0[MAXN], f1[MAXN]; vector<pii> Q[MAXN<<1]; string S; bool cmp(int x, int y, int pw){ if (Rank[pw][x]!=Rank[pw][y]) return Rank[pw][x]<Rank[pw][y]; if (max(x, y)+(1<<pw)>=m) return x>y; return Rank[pw][x+(1<<pw)]<Rank[pw][y+(1<<pw)]; } void BuildSuffixArray(){ for (int i=0; i<m; i++) P[i]=i; sort(P, P+m, [](int i, int j){ return S[i]<S[j];}); for (int i=1; i<m; i++) Rank[0][P[i]]=Rank[0][P[i-1]]+(S[P[i-1]]<S[P[i]]); for (int j=0; j+1<LOG; j++){ int x=0; for (int i=0; i<m; i++) if (P[i]+(1<<j)>=m) P2[x++]=P[i]; for (int i=0; i<m; i++) if ((1<<j)<=P[i]) P2[x++]=P[i]-(1<<j); for (int i=0; i<m; i++) cnt[i]=0; for (int i=0; i<m; i++) cnt[Rank[j][i]]++; for (int i=1; i<m; i++) cnt[i]+=cnt[i-1]; for (int i=m-1; ~i; i--) P[--cnt[Rank[j][P2[i]]]]=P2[i]; for (int i=1; i<m; i++) Rank[j+1][P[i]]=Rank[j+1][P[i-1]] + cmp(P[i-1], P[i], j); } } int GetLcp(int x, int y){ if (x<y) swap(x, y); int res=0; for (int i=LOG-1; ~i && x<m; i--) if (Rank[i][x]==Rank[i][y]){ x+=(1<<i); y+=(1<<i); res|=(1<<i); } return res; } void Maximize(int l, int r, int val){ for (l+=n, r+=n; l<r; l>>=1, r>>=1){ if (l&1) seg[l++]=val; if (r&1) seg[--r]=val; } } int Get(int pos){ int res=-1; for (pos+=n; pos; pos>>=1) res=max(res, seg[pos]); return res; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("72", "r", stdin); //freopen("output.txt", "w", stdout); cin>>S; n=S.size(); S+="#"; // for (int i=n-1; ~i; i--) S+=S[i]; m=S.size(); BuildSuffixArray(); // debug(clock()) int l=-1, r=-1; for (int i=0; i<n; i++){ if (i<=r) f0[i]=min(r-i+1, f0[2*l-i-1]); while (i+f0[i]<n && 0<=i-1-f0[i] && S[i+f0[i]]==S[i-1-f0[i]]) f0[i]++; if (i+f0[i]-1>r){ l=i; r=i+f0[i]-1; } } l=r=-1; for (int i=0; i<n; i++){ if (i<=r) f1[i]=min(r-i+1, f1[2*l-i]); while (i+1+f1[i]<n && 0<=i-1-f1[i] && S[i+1+f1[i]]==S[i-1-f1[i]]) f1[i]++; if (i+f1[i]-1>r){ l=i; r=i+f1[i]; } } for (int i=0; i<n; i++){ int len=f0[i+1]; ans=max(ans, 2ll*len); shit[2*i+1]=i+1-len; } for (int i=0; i<n; i++){ int len=f1[i]+1; ans=max(ans, 2*len-1ll); shit[2*i]=i+1-len; } int ted=0; for (int i=0; i<m; i++) if (P[i]<n) P[ted++]=P[i]; for (int i=0; i+1<n; i++) lcp[i]=GetLcp(P[i], P[i+1]); for (int i=0; i+1<n; i++) for (L[i]=i-1; ~L[i] && lcp[L[i]]>=lcp[i]; L[i]=L[L[i]]); for (int i=n-2; ~i; i--) for (R[i]=i+1; R[i]<n-1 && lcp[R[i]]>=lcp[i]; R[i]=R[R[i]]); for (int i=0; i<=n-2; i++){ ll ted=(R[i]-L[i]); if (!ted) continue ; Q[2*P[i]+lcp[i]].pb({P[i], ted}); } memset(seg, -1, sizeof(seg)); for (int i=0; i<2*n; i++){ for (pii p:Q[i]) ans=max(ans, (Get(p.first)-2*p.first+1ll)*p.second); Maximize(shit[i], i+1, i); } cout<<ans<<'\n'; return 0; } /* abaa */
#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...