Submission #1067508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067508		gs25	Palindromes (APIO14_palindrome)	C++17	47 / 100	1094 ms	19548 KiB

palindrome

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define ff first
#define ss second
using namespace std;
typedef long long ll;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifdef LOCAL
#define dbg(x...)                                                              \
  cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = [";    \
  _print(x);                                                                   \
  cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

const int MAXN = 300100; 
int a[MAXN*2]; 
int lcp[MAXN],sfx[MAXN],ord[MAXN],nord[MAXN],p,n,rev[MAXN];
string s; 

void manacher(string s){
  int k=-1,r=-1; 
  int n = s.size(); 
  for(int i=0; i<n; i++){
    if(i<r) a[i] = min(a[2*k-i],r-i); 
    while(i-a[i]-1>=0 && i+a[i]+1<n && s[i-a[i]-1]==s[i+a[i]+1]) a[i]++; 
    if(i+a[i]>r) r=i+a[i],k=i;
  }
  rep(i,n) a[i] = a[i]-i; 
}

struct shit_{
  int sz = 1<<20; int tree[1<<21] = {}; 
  void build(){
    int nn = n*2; 
    for(int i=sz; i<sz*2; i++){
      if(i-sz<nn) tree[i] = a[i-sz]; 
      else tree[i] = -10000000; 
    }
    for(int i=sz-1; i>0; i--) tree[i] = max(tree[i<<1],tree[(i<<1)|1]); 
  }
  int Max(int l, int r){
    l = l+sz, r = r+sz; 
    int re = -10000000; 
    while(l<=r){
      if(l&1) re = max(re,tree[l++]); 
      if(~r&1) re = max(re,tree[r--]); 
      r>>=1; l>>=1; 
    }
    return re; 
  }
  int query(int i, int j){
    if(j<i) return 0; 
    int l = 2*i,r=i+j; 
    int re = -1; 
    while(l<=r){
      int m = l+r>>1; 
      if(Max(m,r)>=-2*i) re=m,l=m+1; 
      else r=m-1; 
    }
    dbg(i,j,re)
    assert(re>=2*i && re<=i+j); 
    return re-i*2+1; 
  }
}shit; 

bool cmp(int i, int j){
  if(ord[i]!=ord[j]) return ord[i] < ord[j]; 
  i += p; j+= p; 
  return (i<n && j<n) ? ord[i] < ord[j] : i>j; 
}

int cnt[MAXN]; 

void fuck(){
  rep(i,n) ord[i] = s[i], sfx[i] = i; 
  p = 1; int pcnt=0; 
  while(1){
    memset(cnt,0,sizeof(cnt)); 
    for(int i=0; i<n; i++) cnt[ord[min(i+p,n)]]++;
    for(int i=1; i<=n || i<256; i++) cnt[i] += cnt[i-1]; 
    for(int i=0; i<n; i++) nord[--cnt[ord[min(i+p,n)]]] = i;
    memset(cnt,0,sizeof(cnt)); 
    for(int i=0; i<n; i++) cnt[ord[i]]++; 
    for(int i=1; i<=n || i<256; i++) cnt[i] += cnt[i-1]; 
    for(int i=n-1; i>=0; i--) sfx[--cnt[ord[nord[i]]]] = nord[i]; 
    if(pcnt==n-1) break; 
    memset(nord,0,sizeof(nord)); 
    nord[sfx[0]] = 0; 
    for(int i=1; i<n; i++) nord[sfx[i]] = nord[sfx[i-1]] + cmp(sfx[i-1],sfx[i]); 
    pcnt = nord[sfx[n-1]]; 
    memcpy(ord,nord,sizeof(ord)); 
    p*=2; 
  }
  rep(i,n) rev[sfx[i]] = i; 
  for(int i=0,h=0; i<n; i++){
    if(rev[i]!=n-1){
      int nx = sfx[rev[i]+1]; 
      while(nx+h<n && i+h<n && s[nx+h]==s[i+h]) h++; 
      lcp[rev[i]] = h; 
    }
    h = max(h-1,0); 
  }
}

struct rmq_idx_ {
  int sz = 1<<19; int tree[1<<20] = {};  
  void build(){
    for(int i=sz; i<sz*2; i++) tree[i] = i-sz;
    for(int i=sz-1; i>0; i--){
      int ll = tree[i<<1], rr = tree[(i<<1)|1]; 
      if(rr>=MAXN || ll>=MAXN) tree[i] = MAXN; 
      else {
        tree[i] = (lcp[ll] < lcp[rr] ? ll : rr);  
      } 
    }
  }
  int query(int l, int r){
    l = l+sz, r = r+sz; 
    int M = MAXN+100, ans=-1; 
    while(l<=r){
      if(l&1){
        if(lcp[tree[l]]<M) ans = tree[l], M = lcp[tree[l]]; 
        l++; 
      }
      if(~r&1){
        if(lcp[tree[r]]<M) ans=tree[r], M = lcp[tree[r]]; 
        r--; 
      }
      l>>=1; r>>=1; 
    }
    return ans; 
  }
}rmq_idx;

ll ans = 0; 
void dnc(int s, int e){
  if(s==e){
    int pos = sfx[s]; 
    ans = max(ans, (ll)shit.query(pos,n-1)); return; 
  }
  int pos = rmq_idx.query(s,e-1);
  int st = sfx[pos], len = lcp[pos]; 
  dbg(s,e,pos,st,len)
  ans = max(ans,(ll)(e-s+1)*shit.query(st,st+len-1));
  dnc(s,pos);
  dnc(pos+1,e);  
}

void solve(){
  cin >> s; n = s.size(); 
  fuck(); 
  string ss; 
  rep(i,n){
    ss = ss + s[i]; ss += '#'; 
    dbg(i,sfx[i],lcp[i])
  }
  manacher(ss); 
  rmq_idx.build(); 
  shit.build(); 
  dnc(0,n-1); 
  cout << ans; 
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while(t--) solve(); 
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In member function 'int shit_::query(int, int)':
palindrome.cpp:97:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |       int m = l+r>>1;
      |               ~^~

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