Submission #670225

#	Time	Username	Problem	Language	Result	Execution time	Memory
670225		NothingXD	Palindromes (APIO14_palindrome)	C++17	100 / 100	865 ms	26900 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
    ull q = (ull)((L(m) * a) >> 64);
    ull r = a - q * b; // can be proven that 0 <= r < 2*b
    return r >= b ? r - b : r;
  }
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 10;


int base[2] = {313, 369}, mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
int pw[maxn][2];
struct HSH{
	int hsh[maxn][2];
	HSH(){};
	HSH(string s){
		memset(hsh, 0, sizeof hsh);
		int n = s.size();
		for (int i = 1; i <= n; i++){
			for (int j = 0; j < 2; j++){
				hsh[i][j] = (1ll * hsh[i-1][j] * base[j] + s[i-1] - 'a' + 1) % mod[j];
			}
		}
	}
	pii gethsh(int l, int r){
		l--;
		int res[2];
		for (int i = 0; i < 2; i++){
			res[i] = (1ll * hsh[r][i] - 1ll * hsh[l][i] * pw[r-l][i] % mod[i] + 1ll * mod[i]) % mod[i];
		}
		return {res[0], res[1]};
	}
};

int n, suf[maxn], rnk[maxn << 1], tmp[maxn], lcp[maxn], dsu[maxn], a[maxn], cnt[maxn];
int W = 1;
string s;

int getdsu(int v){
	return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}

void merge(int u, int v){
	u = getdsu(u);
	v = getdsu(v);
	dsu[v] = u;
	cnt[u] += cnt[v];
}

bool scmp(int x, int y){
	return (rnk[x] == rnk[y]? rnk[x+W] < rnk[y+W]: rnk[x] < rnk[y]);
}

void suffarr(string &s){
	int n = s.size();
	for (int i = 0; i < n; i++){
		rnk[i] = s[i] - 'a' + 1;
		suf[i] = i;
	}
	for (;; W <<= 1){
		sort(suf, suf + n, scmp);
		tmp[suf[0]] = 1;
		for (int i = 1; i < n; i++){
			tmp[suf[i]] = tmp[suf[i-1]] + scmp(suf[i-1], suf[i]);
		}
		for (int i = 0; i < n; i++) rnk[i] = tmp[i];
		if (rnk[suf[n-1]] == n) return;
	}
}

void buildlcp(string &s){
	int n = s.size();
	int k = 0;
	for (int i = 0; i < n; i++){
		if (rnk[i] == n) continue;
		while (i + k < n && suf[rnk[i]] + k < n && s[i+k] == s[suf[rnk[i]]+k]) k++;
		lcp[rnk[i]] = k;
		if (k) k--;
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	pw[0][0] = pw[0][1] = 1;
	for (int i = 1; i < maxn; i++){
		for (int j = 0; j < 2; j++){
			pw[i][j] = 1ll * pw[i-1][j] * base[j] % mod[j];
		}
	}
	cin >> s;
	string t = s;
	reverse(all(t));
	HSH S(s);
	HSH T(t);
	n = s.size();
	suffarr(s);
	buildlcp(s);

	for (int i = 1; i <= n; i++){
		int l = 0, r = min(i, n-i+2);
		while(l + 1 < r){
			int mid = (l + r) >> 1;
			int tmp = n + 2 - i;
			if (S.gethsh(i-mid, i+mid-1) == T.gethsh(tmp-mid, tmp+mid-1)) l = mid;
			else r = mid;
		}
		a[i] = l;
	}

	vector<pair<pii,int>> Q;

	for (int i = 1; i <= n; i++){
		if (i != n) Q.push_back({{lcp[i], i}, 1});
		Q.push_back({{a[i], rnk[i-1]}, 2});
	}

	memset(dsu, -1, sizeof dsu);
	memset(cnt, 0, sizeof cnt);

	sort(all(Q), greater<pair<pii,int>>());

	ll ans = 0;

	for (auto [x, y]: Q){
		if (y == 1){
			merge(x.S, x.S + 1);
			int v = getdsu(x.S);
			ans = max(ans, 2ll * cnt[v] * x.F);
		}
		else{
			int v = getdsu(x.S);
			cnt[v]++;
			ans = max(ans, 2ll * cnt[v] * x.F);
		}
	}

	for (int i = 1; i <= n; i++){
		int l = 0, r = min(i, n-i+1);
		while(l + 1 < r){
			int mid = (l + r) >> 1;
			int tmp = n + 1 - i;
			if (S.gethsh(i-mid, i+mid) == T.gethsh(tmp-mid, tmp+mid)) l = mid;
			else r = mid;
		}
		a[i] = l+1;
	}

	Q.clear();

	for (int i = 1; i <= n; i++){
		if (i != n) Q.push_back({{lcp[i], i}, 1});
		Q.push_back({{a[i], rnk[i-1]}, 2});
	}

	memset(dsu, -1, sizeof dsu);
	memset(cnt, 0, sizeof cnt);

	sort(all(Q), greater<pair<pii,int>>());

	for (auto [x, y]: Q){
		if (y == 1){
			merge(x.S, x.S + 1);
			int v = getdsu(x.S);
			ans = max(ans, 1ll * (2 * x.F - 1) * cnt[v]);
		}
		else{
			int v = getdsu(x.S);
			cnt[v]++;
			ans = max(ans, 1ll * (2 * x.F - 1) * cnt[v]);
		}
	}

	cout << ans << '\n';

	return 0;
}

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