Submission #538758

#TimeUsernameProblemLanguageResultExecution timeMemory
538758S2speedPalindromes (APIO14_palindrome)C++17
73 / 100
1085 ms80368 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) x.begin() , x.end() #define sze(x) (ll)(x.size()) typedef long long ll; typedef pair<ll , ll> pll; const ll maxn = 3e5 + 16 , P = 131 , md = 2000000357 , inf = 2e16; struct mintree { ll sz = 1; vector<pll> val; pll def; void init(ll n){ while(sz < n) sz <<= 1; def = {inf , -1}; val.assign(sz << 1 , def); return; } void build(vector<ll> &a , ll x , ll lx , ll rx){ if(rx - lx == 1){ if(lx < sze(a)){ val[x] = {a[lx] , lx}; } return; } ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; build(a , ln , lx , m); build(a , rn , m , rx); val[x] = min(val[ln] , val[rn]); } void build(vector<ll> &a){ build(a , 0 , 0 , sz); return; } pll cal(ll l , ll r , ll x , ll lx , ll rx){ if(rx <= l || lx >= r) return def; if(rx <= r && lx >= l) return val[x]; ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; pll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx); return min(a , b); } pll cal(ll l , ll r){ return cal(l , r , 0 , 0 , sz); } }; struct segtree { ll sz = 1; vector<ll> val; void init(ll n){ while(sz < n) sz <<= 1; val.assign(sz << 1 , inf); return; } void set(ll i , ll k , ll x , ll lx , ll rx){ if(rx - lx == 1){ val[x] = k; return; } ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; if(i < m){ set(i , k , ln , lx , m); } else { set(i , k , rn , m , rx); } val[x] = min(val[ln] , val[rn]); return; } void set(ll i , ll k){ set(i , k , 0 , 0 , sz); return; } ll cal(ll l , ll r , ll k , ll x , ll lx , ll rx){ if(rx <= l || lx >= r) return -1; if(val[x] > k) return -1; if(rx - lx == 1) return lx; ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; ll a = cal(l , r , k , rn , m , rx); if(a != -1) return a; return cal(l , r , k , ln , lx , m); } ll cal(ll l , ll r , ll k){ return cal(l , r , k , 0 , 0 , sz); } }; ll n; string s; mintree mt; segtree st[2]; ll sf[maxn] , hs[maxn] , rh[maxn] , tv[maxn]; vector<ll> lcp; ll hum = -1; ll get_hash(ll l , ll r){ if(r >= n) return hum--; ll res = hs[r] - (l ? tv[r - l + 1] * hs[l - 1] : 0); res %= md; res += (res < 0) * md; return res; } bool is_palindrome(ll l , ll r){ if(l < 0 || r >= n) return false; ll h = hs[r] - (l ? tv[r - l + 1] * hs[l - 1] : 0); h %= md; h += (h < 0) * md; ll o = rh[r] - (l ? rh[l - 1] : 0); o %= md; o += (o < 0) * md; h *= tv[l]; h %= md; return (h == o); } ll get_lcp(ll i , ll j){ ll l = 0 , r = n; while(l < r - 1){ ll m = (r + l) >> 1; if(get_hash(i , i + m - 1) == get_hash(j , j + m - 1)){ l = m; } else { r = m; } } return l; } ll t[maxn][2]; ll query(ll i , ll k){ if(k < 2) return k; ll res = 0; ll l = i , r = i + (k + 1) / 2; ll h = st[0].cal(l , r , i); if(h != -1){ res = max(res , 2 * (h - i) + 1); } r = i + k / 2; h = st[1].cal(l , r , i); // cout<<l<<' '<<r<<' '<<i<<' '<<t[l][1]<<' '<<h<<'\n'; if(h != -1){ res = max(res , 2 * (h - i) + 2); } return res; } ll ans = 0; void dv(ll l , ll r){ if(l == r - 1){ ans = max(ans , query(sf[l] , n - sf[l])); } if(l >= r - 1) return; pll h = mt.cal(l , r - 1); ll k = h.first , m = h.second + 1; ans = max(ans , (r - l) * query(sf[l] , k)); dv(l , m); dv(m , r); return; } ll rnk[maxn] , rhk[maxn]; vector<pll> cnt[maxn] , v; ll cal_t(ll i , bool j){ ll l = -1 , r = i + j; while(l < r - 1){ ll m = (r + l) >> 1; if(is_palindrome(m , i + i - m + j)){ r = m; } else { l = m; } } return r; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); tv[0] = 1; for(ll i = 1 ; i < maxn ; i++){ tv[i] = tv[i - 1] * P % md; } cin>>s; n = sze(s); for(ll i = 0 ; i < n ; i++){ rnk[i] = s[i] - 'a' + 1; } ll lm = max(27ll , n + 1); for(ll j = 0 ; j < 20 ; j++){ v.clear(); for(ll i = 0 ; i < lm ; i++){ cnt[i].clear(); cnt[i].shrink_to_fit(); } for(ll i = 0 ; i < n ; i++){ ll o = i + (1 << j); rhk[i] = (o >= n ? 0 : rnk[o]); cnt[rhk[i]].push_back({rnk[i] , i}); } for(ll i = 0 ; i < lm ; i++){ for(auto p : cnt[i]){ v.push_back(p); } } for(ll i = 0 ; i < lm ; i++){ cnt[i].clear(); cnt[i].shrink_to_fit(); } for(auto p : v){ ll i = p.second; cnt[rnk[i]].push_back({rhk[i] , i}); } ll cur = 0; for(ll e = 0 ; e < lm ; e++){ ll pr = -1; for(auto p : cnt[e]){ ll i = p.second , u = p.first; if(pr != u){ cur++; pr = u; } rnk[i] = cur; } } } for(ll i = 0 ; i < n ; i++){ sf[rnk[i] - 1] = i; } rh[0] = hs[0] = s[0]; for(ll i = 1 ; i < n ; i++){ hs[i] = P * hs[i - 1] + s[i]; hs[i] %= md; rh[i] = rh[i - 1] + tv[i] * s[i]; rh[i] %= md; } lcp.resize(n - 1); for(ll e = 0 ; e < n - 1 ; e++){ lcp[e] = get_lcp(sf[e] , sf[e + 1]); } st[0].init(n); st[1].init(n); for(ll i = 0 ; i < n ; i++){ t[i][0] = cal_t(i , 0); st[0].set(i , t[i][0]); t[i][1] = cal_t(i , 1); st[1].set(i , t[i][1]); } mt.init(n); mt.build(lcp); dv(0 , n); cout<<ans<<'\n'; return 0; }
#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...