Submission #414778

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414778	2021-05-31T07:41:32 Z	LastRonin	Palindromes (APIO14_palindrome)	C++14	100 / 100	720 ms	63788 KB

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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	328 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	476 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	2 ms	460 KB	Output is correct
5	Correct	2 ms	588 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	584 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	2 ms	588 KB	Output is correct

Subtask #3
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1984 KB	Output is correct
2	Correct	9 ms	2000 KB	Output is correct
3	Correct	12 ms	2452 KB	Output is correct
4	Correct	13 ms	2448 KB	Output is correct
5	Correct	12 ms	2000 KB	Output is correct
6	Correct	11 ms	1996 KB	Output is correct
7	Correct	9 ms	1996 KB	Output is correct
8	Correct	11 ms	1996 KB	Output is correct
9	Correct	11 ms	1996 KB	Output is correct
10	Correct	16 ms	2440 KB	Output is correct

Subtask #4
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	14736 KB	Output is correct
2	Correct	105 ms	14968 KB	Output is correct
3	Correct	123 ms	18344 KB	Output is correct
4	Correct	137 ms	18500 KB	Output is correct
5	Correct	136 ms	14968 KB	Output is correct
6	Correct	127 ms	14980 KB	Output is correct
7	Correct	127 ms	18232 KB	Output is correct
8	Correct	157 ms	15468 KB	Output is correct
9	Correct	159 ms	15428 KB	Output is correct
10	Correct	208 ms	18436 KB	Output is correct

Subtask #5
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	309 ms	50048 KB	Output is correct
2	Correct	306 ms	49976 KB	Output is correct
3	Correct	406 ms	63276 KB	Output is correct
4	Correct	435 ms	63536 KB	Output is correct
5	Correct	557 ms	50040 KB	Output is correct
6	Correct	391 ms	50916 KB	Output is correct
7	Correct	425 ms	50836 KB	Output is correct
8	Correct	623 ms	51512 KB	Output is correct
9	Correct	600 ms	51512 KB	Output is correct
10	Correct	720 ms	63788 KB	Output is correct
11	Correct	356 ms	50060 KB	Output is correct
12	Correct	586 ms	51536 KB	Output is correct

Submission #414778

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 27.0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
27.0 / 27.0