Submission #348402

#TimeUsernameProblemLanguageResultExecution timeMemory
348402AaeriaPalindromes (APIO14_palindrome)C++14
73 / 100
201 ms131072 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC optimize "unroll-loops" //#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,avx2,fma,mmx,popcnt,tune=native" //#pragma GCC optimize "prefetch-loop-arrays" using namespace std; using namespace __gnu_pbds; #define foru(i,a,b) for(int i=(a);i<(b);i++) #define ford(i,a,b) for(int i=(a);i>=(b);i--) #define fori(a,b) foru(i,a,b) #define forj(a,b) foru(j,a,b) #define fork(a,b) foru(k,a,b) #define seto(x,i) memset(x,i,sizeof x) #define pf first #define ps second #define pb push_back #define eb emplace_back #define em emplace #define mp make_pair #define mt make_tuple #define popcount __builtin_popcount #define popcountll __builtin_popcountll #define clz __builtin_clz #define clzll __builtin_clzll #define ctz __builtin_ctz #define ctzll __builtin_ctzll #define P2(x) (1LL<<(x)) #define sz(x) (int)x.size() #define all(x) begin(x),end(x) #if __SIZEOF_INT128__ typedef __int128_t i128; typedef __uint128_t ui128; #else typedef int64_t i128; typedef uint64_t ui128; #endif typedef int64_t ll; typedef uint64_t ull; typedef int8_t byte; typedef long double lld; typedef string str; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<lld,lld> pdd; template<class T1,class T2> using ordered_map=tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>; template<class T1> using ordered_set=ordered_map<T1,null_type>; template<class T> using minpq=std::priority_queue<T,vector<T>,greater<T>>; template<class T> using maxpq=std::priority_queue<T,vector<T>,less<T>>; template<class T> using minpairingheap=__gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>; template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>; const int inf=0x3f3f3f3f,MOD=1e9+7; const ll INF=0x3f3f3f3f3f3f3f3f; const lld PI=acos((lld)-1); const ll SEED=443214^chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(); mt19937 randgen(SEED); int randint(int a, int b){return uniform_int_distribution<int>(a,b)(randgen);} ll randll(ll a, ll b){return uniform_int_distribution<ll>(a,b)(randgen);} ll gcd(ll a, ll b){return b?gcd(b,a%b):a;} ll fpow(ll a,ll b){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%MOD;a=a*a%MOD;}return ret;} template<class T1,class T2>constexpr const auto _min(const T1&x,const T2&y){return x<y?x:y;} template<class T,class...Ts>constexpr auto _min(const T&x,const Ts&...xs){return _min(x,_min(xs...));} template<class T1,class T2>constexpr const auto _max(const T1&x,const T2&y){return x>y?x:y;} template<class T,class...Ts>constexpr auto _max(const T&x,const Ts&...xs){return _max(x,_max(xs...));} #define min(...) _min(__VA_ARGS__) #define max(...) _max(__VA_ARGS__) template<class T1,class T2>constexpr const bool ckmin(T1&x,const T2&y){return x>y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmin(T&x,const Ts&...xs){return ckmin(x,_min(xs...));} template<class T1,class T2>constexpr const bool ckmax(T1&x,const T2&y){return x<y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmax(T&x,const Ts&...xs){return ckmax(x,_max(xs...));} struct chash{ static ll splitmix64(ll x){x+=0x9e3779b97f4a7c15; x=(x^(x>>30))*0xbf58476d1ce4e5b9; x=(x^(x>>27))*0x94d049bb133111eb; return x^(x>>31);} template<class T> size_t operator()(const T &x) const{return splitmix64(hash<T>()(x)+SEED);} template<class T1,class T2> size_t operator()(const pair<T1,T2>&x)const{return 31*operator()(x.first)+operator()(x.second);}}; void fileIn(string s){freopen(s.c_str(),"r",stdin);} void fileOut(string s){freopen(s.c_str(),"w",stdout);} void fileIO(string s){fileIn(s+".in"); fileOut(s+".out");} string to_string(char c){return string(1,c);} string to_string(char* s){return (string)s;} string to_string(string s){return s;} template<class T> string to_string(complex<T> c){stringstream ss; ss<<c; return ss.str();} template<class T1,class T2> string to_string(pair<T1,T2> p){return "("+to_string(p.pf)+","+to_string(p.ps)+")";} template<size_t SZ> string to_string(bitset<SZ> b){string ret=""; fori(0,SZ) ret+=char('0'+b[i]); return ret;} template<class T> string to_string(T v){string ret="{"; for(const auto& x:v) ret+=to_string(x)+","; return ret+"}";} void DBG(){cerr<<"]"<<endl;} template<class T,class... Ts> void DBG(T x,Ts... xs){cerr<<to_string(x); if(sizeof...(xs)) cerr<<", "; DBG(xs...);} #ifdef LOCAL_PROJECT #define dbg(...) cerr<<"Line("<< __LINE__<<") -> ["<<#__VA_ARGS__<<"]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif #define nl "\n" const int N=600010,M=MOD; int n,oc[N],pal[N],num[N],x,last,rt[N]; ll ans; maxpq<int> len[N]; struct node{ int len,p,nxt[26]; }; struct SuffixAutomaton{ int last; vector<node> st; void init(string s){ st.clear(); last=0; st.emplace_back(); st[0].p=-1; for(auto i:s) ins(i-'a'); } void ins(int c){ int cur=st.size(),p=last; st.emplace_back(); oc[cur]=1; st[cur].len=st[last].len+1; if(st[cur].len) num[st[cur].len-1]=cur; while(p!=-1&&!st[p].nxt[c]){ st[p].nxt[c]=cur; p=st[p].p; } if(p==-1) st[cur].p=0; else{ int q=st[p].nxt[c]; if(st[q].len==st[p].len+1) st[cur].p=q; else{ int clone=st.size(); st.pb(st[q]); st[clone].len=st[p].len+1; while(p!=-1&&st[p].nxt[c]==q){ st[p].nxt[c]=clone; p=st[p].p; } st[q].p=st[cur].p=clone; } } last=cur; } } sa; str s; vector<int> gr[N]; char in[N]; int szdfs(int v){ for(auto i:gr[v]) oc[v]+=szdfs(i); return oc[v]; } void dfs(int v){ rt[v]=v; for(auto i:gr[v]){ dfs(i); for(;sz(len[rt[i]])&&len[rt[i]].top()>sa.st[v].len;len[rt[i]].pop()) ckmax(ans,1LL*len[rt[i]].top()*oc[i]); if(sz(len[rt[i]])>sz(len[rt[v]])) swap(rt[i],rt[v]); for(;sz(len[rt[i]]);len[rt[i]].pop()) len[rt[v]].em(len[rt[i]].top()); } } int main(){ cin.tie(0)->sync_with_stdio(0); cin>>s; n=sz(s); sa.init(s); fori(1,sz(sa.st)) gr[sa.st[i].p].pb(i); szdfs(0); in[n*2]='#'; fori(0,n){ in[i*2+1]=s[i]; in[i*2]='#'; } n=n*2+1; fori(1,n){ for(pal[i]=i>=x? 1: min(x-i,pal[last*2-i]);i-pal[i]>=0&&i+pal[i]<n&&in[i-pal[i]]==in[i+pal[i]];pal[i]++); if(i+pal[i]>x) x=i+pal[i],last=i; } fori(1,n-1){ pal[i]--; dbg((i-pal[i])/2,(i+pal[i]-2)/2); len[num[(i+pal[i]-2)/2]].em((i+pal[i]-2)/2-(i-pal[i])/2+1); } dfs(0); cout<<ans; return 0; } /** overflow pal[i]-- i-pal[i]+1 , i+pal[i]-1 (i+pal[i]-2)/2 */

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:63:22: warning: statement has no effect [-Wunused-value]
   63 |     #define dbg(...) 0
      |                      ^
palindrome.cpp:139:9: note: in expansion of macro 'dbg'
  139 |         dbg((i-pal[i])/2,(i+pal[i]-2)/2);
      |         ^~~
palindrome.cpp: In function 'void fileIn(std::string)':
palindrome.cpp:54:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 | void fileIn(string s){freopen(s.c_str(),"r",stdin);} void fileOut(string s){freopen(s.c_str(),"w",stdout);} void fileIO(string s){fileIn(s+".in"); fileOut(s+".out");}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
palindrome.cpp: In function 'void fileOut(std::string)':
palindrome.cpp:54:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 | void fileIn(string s){freopen(s.c_str(),"r",stdin);} void fileOut(string s){freopen(s.c_str(),"w",stdout);} void fileIO(string s){fileIn(s+".in"); fileOut(s+".out");}
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...