제출 #414734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414734		LastRonin	회문 (APIO14_palindrome)	C++14	0 / 100	316 ms	79216 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 = 4e5 + 10;

int n;
string b;
int a[21][N], suf[N];
pair<ll, int> c[N];
vector<pair<ll, ll>> x;

vector<ll> srt[N];
vector<ll> srt2[N];

void sufmas() {

	for(int j = 1; j <= n; j++) {
		a[0][j] = b[j - 1] - 'a' + 1;
	}
	ll k = __lg(n - 1) + 1;
	for(int j = 1; j <= k; j++) {
		for(int i = 1; i <= n; i++)
			srt[a[j - 1][i + (1<<(j-1))]].pb(i);
		for(int i = 1; i <= max(26, n); i++)
			for(auto u : srt[i])
				srt2[a[j - 1][u]].pb(u);
		ll cur = 1, cnt = 0;
		for(int i = 1; i <= max(26, n); i++) {
		    ll lst = -1;
			for(auto u : srt2[i]) {	
				if(a[j - 1][u +(1<<(j-1))] != lst)
					lst = a[j - 1][u +(1<<(j-1))], cnt++; 														
				a[j][u] = cnt, suf[u] = cnt;
			}
			srt2[i].clear(), srt[i].clear();
		}
	}
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'void sufmas()':
palindrome.cpp:35:6: warning: unused variable 'cur' [-Wunused-variable]
   35 |   ll cur = 1, cnt = 0;
      |      ^~~

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