Submission #601480

#	Time	Username	Problem	Language	Result	Execution time	Memory
601480		penguinhacker	Palinilap (COI16_palinilap)	C++17	54 / 100	435 ms	81792 KiB

palinilap

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

#define ll long long
#define ar array

const int M=1e9+696969;
const ar<int, 2> B={1091, 291972};

ar<int, 2> operator+ (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		if ((a[i] += b[i]) >= M)
			a[i] -= M;
	return a;
}

ar<int, 2> operator- (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		if ((a[i] -= b[i]) < 0)
			a[i] += M;
	return a;
}

ar<int, 2> operator* (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		a[i] = (ll)a[i] * b[i] % M;
	return a;
}

ar<int, 2> mk(char c) {
	return {c, c};
}

const int mxN=1e5+5;
int n, d1[mxN], d2[mxN], change[26][mxN];
string s;
ar<int, 2> p[mxN], h1[mxN+1], h2[mxN+1];
ll bad[mxN], pref[mxN];
vector<ar<int, 2>> cands[mxN][26];

ar<int, 2> get1(int l, int r, ar<int, 2> change={}) {
	return h1[r+1]-h1[l]*p[r-l+1]+change;
}

ar<int, 2> get2(int l, int r, ar<int, 2> change={}) {
	return h2[l]-h2[r+1]*p[r-l+1]+change;
}

bool ck(int l, int r, int i=-1, ar<int, 2> change={}) {
	assert(0<=l&&l<=r&&r<n);
	if (i<l||i>r)
		return get1(l, r)==get2(l, r);
	return get1(l, r)+change*p[r-i]==get2(l, r)+change*p[i-l];
}

int solve1(int i, int pos=-1, ar<int, 2> change={}) { // get number of palindromes centered at s[i]
	assert(0<=i&&i<n);
	int lb=1, rb=min(i+1, n-i);
	while(lb<rb) {
		int mid=(lb+rb+1)/2;
		if (ck(i-mid+1, i+mid-1, pos, change))
			lb=mid;
		else
			rb=mid-1;
	}
	return lb;
}

int solve2(int i, int pos=-1, ar<int, 2> change={}) { // get number of palindromes centered at s[i]-s[i+1]
	assert(0<=i&&i<n-1);
	//if (s[i]!=s[i+1]&&pos==-1)
	//	return 0;
	int lb=0, rb=min(i+1, n-1-i);
	while(lb<rb) {
		int mid=(lb+rb+1)/2;
		if (ck(i-mid+1, i+mid, pos, change))
			lb=mid;
		else
			rb=mid-1;
	}
	return lb;
}

void add_seg(int l, int r) {
	assert(0<=l&&l<=r&&r<n);
	++pref[l], --pref[r+1];
	bad[r+1]-=r-l+1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s, n=s.size();
	p[0]={1, 1};
	for (int i=1; i<n; ++i)
		p[i]=p[i-1]*B;
	for (int i=0; i<n; ++i)
		h1[i+1]=h1[i]*B+mk(s[i]);
	for (int i=n-1; ~i; --i)
		h2[i]=h2[i+1]*B+mk(s[i]);
	ll base=0;
	for (int i=0; i<n; ++i) {
		d1[i]=solve1(i);
		d2[i]=i+1<n?solve2(i):0;
		base+=d1[i]+d2[i];
	}
	for (int rep=0; rep<2; ++rep) {
		for (int i=0; i<n; ++i) {
			if (d1[i]>1)
				add_seg(i-d1[i]+1, i-1);
			if (i-d1[i]+1&&i+d1[i]<n)
				cands[i-d1[i]][s[i+d1[i]]-'a'].push_back({i, 1});
		}
		for (int i=0; i+1<n; ++i) {
			if (d2[i])
				add_seg(i-d2[i]+1, i);
			if (i-d2[i]+1&&i+d2[i]+1<n)
				cands[i-d2[i]][s[i+d2[i]+1]-'a'].push_back({i, 2});
		}
		for (int i=0; i<n; ++i) {
			if (i) {
				pref[i]+=pref[i-1];
				bad[i]+=bad[i-1];
			}
			bad[i]+=pref[i];
			for (int j=0; j<26; ++j) {
				if (s[i]=='a'+j)
					continue;
				change[j][i]-=bad[i];
				for (auto [c, t] : cands[i][j])
					change[j][i]+=t==1?solve1(c, i, mk('a'+j)-mk(s[i]))-d1[c]:solve2(c, i, mk('a'+j)-mk(s[i]))-d2[c];
			}
		}
		reverse(d1, d1+n);
		reverse(d2, d2+n-1);
		for (int j=0; j<26; ++j)
			reverse(change[j], change[j]+n);
		memset(bad, 0, sizeof(bad));
		memset(pref, 0, sizeof(pref));
		for (int i=0; i<n; ++i)
			for (int j=0; j<26; ++j)
				cands[i][j].clear();
		reverse(s.begin(), s.end());
		for (int i=0; i<n; ++i)
			h1[i+1]=h1[i]*B+mk(s[i]);
		for (int i=n-1; ~i; --i)
			h2[i]=h2[i+1]*B+mk(s[i]);

	}
	ll ans=base;
	for (int i=0; i<26; ++i)
		ans=max(ans, base+*max_element(change[i], change[i]+n));
	cout << ans;
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 0 / 46