oj.uz

Submission #601482

# Submission time Handle Problem Language Result Execution time Memory
601482 2022-07-22T05:36:49 Z penguinhacker Palinilap (COI16_palinilap) C++17
100 / 100
 483 ms 98356 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

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

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;
int n, d1[mxN], d2[mxN];
string s;
ar<int, 2> p[mxN], h1[mxN+1], h2[mxN+1];
ll bad[mxN], pref[mxN], change[26][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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63024 KB Output is correct
2 Correct 34 ms 63052 KB Output is correct
3 Correct 31 ms 63120 KB Output is correct
4 Correct 31 ms 63128 KB Output is correct
5 Correct 31 ms 63060 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64444 KB Output is correct
2 Correct 40 ms 64476 KB Output is correct
3 Correct 45 ms 64380 KB Output is correct
4 Correct 51 ms 63948 KB Output is correct
5 Correct 46 ms 64460 KB Output is correct
6 Correct 45 ms 64548 KB Output is correct
7 Correct 44 ms 64464 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 90132 KB Output is correct
2 Correct 317 ms 92044 KB Output is correct
3 Correct 236 ms 90492 KB Output is correct
4 Correct 388 ms 91336 KB Output is correct
5 Correct 406 ms 91236 KB Output is correct
6 Correct 410 ms 93956 KB Output is correct
7 Correct 416 ms 93832 KB Output is correct
8 Correct 135 ms 86608 KB Output is correct
9 Correct 398 ms 91276 KB Output is correct
10 Correct 483 ms 93824 KB Output is correct
11 Correct 336 ms 92024 KB Output is correct
12 Correct 368 ms 92764 KB Output is correct
13 Correct 405 ms 90952 KB Output is correct
14 Correct 408 ms 94184 KB Output is correct
15 Correct 406 ms 94000 KB Output is correct
16 Correct 349 ms 92428 KB Output is correct
17 Correct 409 ms 98356 KB Output is correct
18 Correct 394 ms 91448 KB Output is correct
19 Correct 401 ms 92748 KB Output is correct