Submission #957307

#	Time	Username	Problem	Language	Result	Execution time	Memory
957307		vjudge1	Palindromes (APIO14_palindrome)	C++14	100 / 100	346 ms	69924 KiB

palindrome

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct SuffixArray {
	vi sa, lcp;
	SuffixArray(string& s, int lim=256) { // or basic_string<int>
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1ll, j * 2), lim = p) {
			p = j, iota(all(y), n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		rep(i,1,n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
					s[i + k] == s[j + k]; k++);
	}
};

array<vi, 2> manacher(const string& s) {
	int n = sz(s);
	array<vi,2> p = {vi(n+1), vi(n)};
	rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {
		int t = r-i+!z;
		if (i<r) p[z][i] = min(t, p[z][l+t]);
		int L = i-p[z][i], R = i+p[z][i]-!z;
		while (L>=1 && R+1<n && s[L-1] == s[R+1])
			p[z][i]++, L--, R++;
		if (R>r) l=L, r=R;
	}
	return p;
}

const int N=3e5+10;
int l[N], r[N];

int solve(vector<int> a){
   int n=a.size()-1;
   stack<int> st;
   for (int i=1; i<=n; ++i){
      while (st.size() && a[st.top()]>=a[i]) st.pop();
      l[i]=st.empty()?1:st.top()+1;
      st.push(i);
   }
   while (st.size()) st.pop();
   for (int i=n; i>=1; --i){
      while (st.size() && a[st.top()]>=a[i]) st.pop();
      r[i]=st.empty()?n:st.top()-1;
      st.push(i);
   }
   int ans=0;
   for (int i=1; i<=n; ++i) ans=max(ans, a[i]*(r[i]-l[i]+2));
   return ans;
}

vector<int> vv[N];
int len[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   string s; cin >> s;
   SuffixArray sa(s, 128);
   auto v=manacher(s);
   vector<pair<int, int>> pal;
   int n=s.size();
   for (int i=0; i<n; ++i) pal.emplace_back(i-v[1][i], i+v[1][i]);
   for (int i=0; i<n; ++i) if (v[0][i]) pal.emplace_back(i-v[0][i], i+v[0][i]-1);
   for (auto &i:pal) vv[i.first].push_back(i.second);
   priority_queue<pair<int, int>> pq;
   int ans=0;
   for (int i=0; i<n; ++i){
      for (int j:vv[i]) pq.emplace(i+j, (i+j)/2);
      while (pq.size() && pq.top().second<i) pq.pop();
      len[i]=pq.size()?pq.top().first+1-i*2:0;
      ans=max(ans, len[i]);
   }
   auto lcp=sa.lcp;
   for (int i=1; i<=n; ++i){
      lcp[i]=min(lcp[i], len[sa.sa[i]]);
      if (i>1) lcp[i]=min(lcp[i], len[sa.sa[i-1]]);
   }
   ans=max(ans, solve(lcp));
   cout << ans;
   return 0;
}

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