| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 73588 | polyfish | Palindromes (APIO14_palindrome) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 300002;
struct fenwick_tree {
int n;
vector<int> bit;
void init(int _n) {
n = _n;
bit.resize(n+1);
}
void upd(int id) {
++id;
for (; id<=n; id += id & (-id))
++bit[id];
}
int get(int id) {
++id;
int res = 0;
for (; id>0; id -= id & (-id))
res += bit[id];
return res;
}
int get(int l, int r) {
return get(r) - get(l-1);
}
};
int n, gap, L[MAX_N], R[MAX_N], d1[MAX_N], d2[MAX_N];
int pos[MAX_N], sa[MAX_N], lcp[MAX_N], tmp[MAX_N];
string s;
set<pair<int, int> > seg;
fenwick_tree tr;
void enter() {
char c;
while (cin >> c) {
s += '#';
s += c;
}
s += '#';
n = s.size();
}
void manacher() {
for (int i=0, l=0, r=-1; i<n; ++i) {
int k = i>r ? 1 : min(R[l+r-i], r-i);
while (i+k<n && i-k>=0 && s[i+k]==s[i-k])
++k;
d1[i] = k--;
if (i+k>r) {
l = i - k;
r = i + k;
}
}
}
bool cmp(int i, int j) {
if (pos[i]!=pos[j])
return pos[i] < pos[j];
i += gap;
j += gap;
return i<n && j<n ? pos[i] < pos[j] : i > j;
}
void build_SA() {
for (int i=0; i<n; ++i) {
sa[i] = i;
pos[i] = s[i];
}
for (gap = 1; ; gap *= 2) {
sort(sa, sa+n, cmp);
for (int i=1; i<n; ++i)
tmp[i] = tmp[i-1] + cmp(sa[i-1], sa[i]);
for (int i=0; i<n; ++i)
pos[sa[i]] = tmp[i];
if (tmp[n-1]==n-1)
break;
}
}
void build_LCP() {
for (int i=0, k=0; i<n; ++i) {
if (pos[i]!=n-1) {
for (int j=sa[pos[i]+1]; i+k<n && j+k<n && s[i+k]==s[j+k];)
++k;
lcp[pos[i]] = k;
if (k)
--k;
}
}
}
void find_min_boundary() {
stack<int> st;
for (int i=0; i<n; ++i) {
while (st.size() && lcp[st.top()]>=lcp[i])
st.pop();
if (st.size())
L[i] = st.top() + 1;
else
L[i] = 0;
st.push(i);
}
while (st.size())
st.pop();
for (int i=n-1; i>=0; --i) {
while (st.size() && lcp[st.top()]>=lcp[i])
st.pop();
if (st.size())
R[i] = st.top() - 1;
else
R[i] = n-1;
st.push(i);
}
}
int add_seg(int l, int r) {
while (seg.size()) {
set<pair<int, int> >::iterator it = seg.lower_bound(make_pair(l, l));
if (it!=seg.end() && it->second<=r)
seg.erase(it);
else
break;
}
seg.insert(make_pair(l, r));
return tr.get(l, r);
}
int add_pos(int pos) {
int res = 0;
tr.upd(pos);
if (seg.empty())
return 0;
set<pair<int, int> >::iterator it = seg.upper_bound(make_pair(pos, n+1));
while (it!=seg.begin()) {
--it;
//cerr << it->first << ' ' << it->second << '\n';
if (it->second<pos)
break;
res = max(res, tr.get(it->first, it->second));
}
return res;
}
void solve() {
for (int i=0; i<n; ++i)
d2[i] = d1[sa[i]];
vector<pair<int, int> > b1, b2;
for (int i=0; i<n; ++i) {
b1.push_back(make_pair(lcp[i], i));
b2.push_back(make_pair(d2[i], i));
}
sort(b1.begin(), b1.end());
sort(b2.begin(), b2.end());
tr.init(n);
int max_cnt = 0;
int64_t res = 0;
if (d1[n/2]==n/2+1)
res = n/2;
for (int i=n/2; i>=1; --i) {
while (b1.size() && b1.back().first>=i) {
max_cnt = max(max_cnt, add_seg(L[b1.back().second], R[b1.back().second] + 1));
b1.pop_back();
}
while (b2.size() && b2.back().first>=i) {
max_cnt = max(max_cnt, add_pos(b2.back().second));
b2.pop_back();
}
res = max(res, 1LL * (i - 1) * max_cnt);
//debug(res);
}
cout << res;
}
int main() {
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
manacher();
build_SA();
build_LCP();
find_min_boundary();
solve();
}