oj.uz

답안 #601478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601478 2022-07-22T05:33:02 Z penguinhacker Palinilap (COI16_palinilap) C++17
54 / 100
 381 ms 81808 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};

#define dbg(x) cerr << "[" << #x << "] = [" << x << "]\n"

template<class A, size_t sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
	out << '[';
	for (int i = 0; i < sz; ++i) {
		if (i > 0) out << ", ";
		out << a[i];
	}
	return out << ']';
}

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], 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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 63060 KB Output is correct
2 Correct 36 ms 63052 KB Output is correct
3 Correct 30 ms 63040 KB Output is correct
4 Correct 31 ms 63104 KB Output is correct
5 Correct 30 ms 63052 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 63876 KB Output is correct
2 Correct 37 ms 63836 KB Output is correct
3 Correct 46 ms 63884 KB Output is correct
4 Correct 39 ms 63740 KB Output is correct
5 Correct 39 ms 63948 KB Output is correct
6 Correct 42 ms 64064 KB Output is correct
7 Correct 42 ms 64048 KB Output is correct

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 79948 KB Output is correct
2 Incorrect 285 ms 81808 KB Output isn't correct
3 Halted 0 ms 0 KB -