Submission #1129611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129611		Tob	Palindromes (APIO14_palindrome)	C++20	100 / 100	457 ms	73212 KiB

palindrome

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 3e5 + 7, alp = 256;
const int B = 31357, mod = 1e9 + 7;

int n;
int p[N], p2[N], c[N], c2[N], fr[N], lcp[N], pos[N], h[N], rh[N], pot[N], r[N][2];
vector <pii> qu[N];
vector <int> dod[N][2];
string s;

inline int addp(int x, int y) {return (x+y<n) ? x+y : x+y-n;}
inline int subp(int x, int y) {return (x-y>=0) ? x-y : x-y+n;}

inline int addm(int x, int y) {return (x+y<mod) ? x+y : x+y-mod;}
inline int mulm(int x, int y) {return (ll)x*y%mod;}

inline int ha(int x, int y) {return addm(h[y+1], mod-mulm(h[x], pot[y-x+1]));}
inline int rha(int x, int y) {return addm(rh[x], mod-mulm(rh[y+1], pot[y-x+1]));}

int main () {
	FIO;
	pot[0] = 1;
	for (int i = 1; i < N; i++) pot[i] = mulm(pot[i-1], B);
	cin >> s; s += '$'; n = s.size();
	
	for (int i = 0; i < n; i++) fr[s[i]]++;
	for (int i = 1; i < alp; i++) fr[i] += fr[i-1];
	for (int i = 0; i < n; i++) p[--fr[s[i]]] = i;
	int cnt = 1;
	for (int i = 0; i < n; i++) {
		cnt += (i && s[p[i-1]] != s[p[i]]);
		c[p[i]] = cnt-1;
	}
	for (int j = 1; j < n; j *= 2) {
		fill(fr, fr+cnt, 0);
		for (int i = 0; i < n; i++) p2[i] = subp(p[i], j);
		for (int i = 0; i < n; i++) fr[c[i]]++;
		for (int i = 1; i < cnt; i++) fr[i] += fr[i-1];
		for (int i = n-1; i >= 0; i--) p[--fr[c[p2[i]]]] = p2[i];
		cnt = 1;
		for (int i = 0; i < n; i++) {
			cnt += (i && (c[p[i-1]] != c[p[i]] || c[addp(p[i-1], j)] != c[addp(p[i], j)]));
			c2[p[i]] = cnt-1;
		}
		swap(c, c2);
	}
	
	for (int i = 0; i < n; i++) h[i+1] = addm(mulm(h[i], B), s[i]);
	for (int i = n-1; i >= 0; i--) rh[i] = addm(mulm(rh[i+1], B), s[i]);
	
	for (int i = 0; i < n; i++) pos[p[i]] = i;
	int k = 0;
    for (int i = 0; i < n; i++) {
        if (pos[i] == n-1) {
            k = 0;
            continue;
        }
        int j = p[pos[i]+1];
        while (i+k < n && j+k < n && s[i+k] == s[j+k]) k++;
        lcp[pos[i]] = k;
        if (k) k--;
    }
    
    stack <pii> st;
    for (int i = 1; i <= n; i++) {
    	ll le = 0;
    	while (!st.empty() && st.top().F >= lcp[i-1]) {
			le += st.top().S;
			qu[p[i-1]].pb({st.top().F, le});
			st.pop();
		}
		st.push({lcp[i-1], le});
		st.push({n-p[i]-1, 1});
	}
	
	for (int o = 0; o < 2; o++) {
		for (int i = 0; i < n-1; i++) {
			int lo = -1, hi = min(i, n-i-1-o);
			while (lo < hi) {
				int mid = (lo+hi+1)/2;
				if (ha(i+o, i+o+mid) == rha(i-mid, i)) lo = mid;
				else hi = mid-1;
			}
			if (lo != -1) dod[i-lo][o].pb(i);
		}
	}
	
    ll mx = 0;
	set <int> ss;
	for (int o = 0; o < 2; o++) {
		for (int i = 0; i < n-1; i++) {
			for (auto x : dod[i][o]) ss.insert(x);
			for (auto x : qu[i]) {
				auto pp = ss.lower_bound(i+(x.F+1-o)/2);
				if (pp != ss.begin()) mx = max(mx, x.S*(2*(*(--pp)-i)+o+1));
			}
		}
		ss.clear();
	}
	cout << mx << "\n";

	return 0;
}

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