Submission #414778

#	Time	Username	Problem	Language	Result	Execution time	Memory
414778		LastRonin	Palindromes (APIO14_palindrome)	C++14	100 / 100	720 ms	63788 KiB

palindrome

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pill pair<ll, ll>
#define pb push_back
using namespace std;

const ll N = 3e5 + 10;

int n;
string b;
int a[21][N], suf[N];
vector<pair<int, int>> x;
int bl[N], bl2[N], c[N], L[N], z[N];

void sufmas() {
	for(int j = 1; j <= n; j++) {
		a[0][j] = b[j - 1] - 'a' + 1;
	}
	ll k = __lg(n - 1) + 1;
	int p = 1;
	for(int j = 1; j <= k; j++) {
		int r = 0, r2 = 0, sum = 0, sum2 = 0, cnt = 0;
		z[0] = -1;
		for(int i = 1; i <= n; i++) {
			z[i] = (i+p>n?0:a[j - 1][i + p]);
			r = max(z[i], r), r2 = max(r2, a[j - 1][i]);
			bl2[z[i]]++;
		}
		for(int i = 0; i <= r; i++) L[i] = sum, sum += bl2[i], bl2[i] = 0;						
		for(int i = 1; i <= n; i++) bl[L[z[i]]++] = i, bl2[a[j - 1][i]]++;
		for(int i = 1; i <= r2; i++) L[i] = sum2 + 1, sum2 += bl2[i], bl2[i] = 0;
		for(int i = 0; i < n; i++) c[L[a[j-1][bl[i]]]++] = bl[i];
		for(int i = 1; i <= n; i++) {
			cnt += (z[c[i - 1]] != z[c[i]] || a[j - 1][c[i - 1]] != a[j - 1][c[i]]);							
			a[j][c[i]] = cnt, suf[c[i]] = cnt;
		}
		p <<= 1;
	}

	for(int i = 1; i <= n; i++)
		x.pb(mp(suf[i], i));
	sort(x.begin(), x.end());
}

int dp[N], dp2[N];
vector<pair<ll, pill>> que;

void manaker() {
	for(int i = 1, r = 0, m = 0; i <= n; i++) {
		if(i <= r)
			dp[i] = min(r - i, dp[m - i + m]);		
		while(i + dp[i] <= n && i > dp[i] && b[i + dp[i] - 1] == b[i - dp[i] - 1])
			dp[i]++;
		if(i + dp[i] - 1 > r)
			r = i + dp[i] - 1, m = i;	
	}
	for(int i = 1, r = 0, m = 0; i <= n; i++) {
		if(i <= r)
			dp2[i] = min(r - i, dp2[m - (i - m - 1) - 1]);
		while(i + dp2[i] + 1 <= n && i > dp2[i] && b[i + dp2[i]] == b[i - dp2[i] - 1])
			dp2[i]++;
		if(i + dp2[i] > r)
			r = i + dp2[i], m = i;
	}
	queue<pill> r;
	for(int i = 1; i <= n; i++) {
		while(r.size() && r.front().s < i)
			r.pop();
		r.push(mp(i,i + dp[i] - 1));
		ll z = r.front().f;
		que.pb(mp(suf[z - i + z],mp((z - i + z), i)));
	}
	while(r.size())r.pop();
	for(int i = 1; i <= n; i++) {
		while(r.size() && r.front().s < i)
			r.pop();
		r.push(mp(i, i + dp2[i]));
		ll z = r.front().f;
		if(i == z)continue;
		que.pb(mp(suf[z - i + z + 1], mp(z - (i - z - 1), i)));	
	}
}

ll comp(ll l1, ll r1, ll l2, ll r2) {
	ll mn = __lg(min(r1 - l1 + 1, r2 - l2 + 1));
	ll d = min(r1 - l1 + 1, r2 - l2 + 1);
	if(a[mn][l1] == a[mn][l2]) {
		ll z = (l1 + d - 1) - (1<<mn) + 1;
		ll z2 = (l2 + d - 1) - (1<<mn) + 1;
		if(a[mn][z] == a[mn][z2]) {
			if(r1 - l1 + 1 <= r2 - l2 + 1)
				return 2;
			return 0;	
		}	
	   	return  a[mn][z] < a[mn][z2];
	}
	return (a[mn][l1] < a[mn][l2]);
}

int main() {
	speed;
	cin >> b;
	n = b.size();
	sufmas();
	manaker();
	sort(que.begin(), que.end());
	ll ans = 0;
	for(auto u : que) {
	    ll L = 0, R = n - 1, l = -1, r = -1;
	    while(L <= R) {
			ll m = (L + R) >> 1ll;
			ll z = comp(u.s.f, u.s.s, x[m].s, n);
			if(z == 2) 
				l = m;
			if(z >= 1)
				R = m - 1;	
			else
				L = m + 1;
	    }
	    L = 0, R = n - 1, r = -1;
		while(L <= R) {
			ll m = (L + R) >> 1ll;
			ll z = comp(u.s.f, u.s.s, x[m].s, n);
			if(z == 2)
				r = m;
			if(z == 1)
				R = m - 1;
			else if( z == 2)
				L = m + 1;
			else
				L = m + 1;					
		}
		ans = max(ans, (r - l + 1) * (u.s.s - u.s.f + 1));
 	}
 	cout << ans;
}

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