Submission #140594

#	Time	Username	Problem	Language	Result	Execution time	Memory
140594		aarr	Palinilap (COI16_palinilap)	C++14	100 / 100	446 ms	35088 KiB

palinilap

#include <iostream>
#include <set>
#include <map>
#include <vector>
using namespace std;

const int N = 100 * 1000 + 5, mod = 1000 * 1000 * 1000 + 21;
int n;

string s;
long long pow29[N];
long long pre[N];
long long suf[N];
long long ad[N][32];
map < pair <int, char>, long long > mp;
long long d[N];
vector <pair <int, char> > v;
long long ads[N];
long long ps[N];
long long ps2[N];
long long adsr[N];
long long psr[N];
long long ps2r[N];

bool isPal(int l, int r) {
	long long lp, sp = 0, ls, ss = 0;
	lp = pre[r];
	if (l > 0)
		sp = pre[l - 1];
	ls = suf[l];
	ss = suf[r + 1];
//	cout << sp << " " << lp << " " << ss << " " << ls << endl;
	long long x, y;
	x = lp - sp * pow29[r - l + 1], y = ls - ss * pow29[r - l + 1];
	if (x < 0) 
		x += (-(x / mod) + 1) * mod;
	if (y < 0)
		y += (-(y / mod) + 1) * mod;
	x %= mod;
	y %= mod;
//	cout << l << " " << r << " " << x << " " << y << endl;
	return x == y;
}

bool isPalChng(int l, int r, int a, int b) {
	long long lp, sp = 0, ls, ss = 0;
	lp = pre[r];
	if (l > 0)
		sp = pre[l - 1];
	ls = suf[l];
	ss = suf[r + 1];
//	cout << sp << " " << lp << " " << ss << " " << ls << endl;
	long long x, y;
	x = lp - sp * pow29[r - l + 1], y = ls - ss * pow29[r - l + 1];
	if (x < 0) 
		x += (-(x / mod) + 1) * mod;
	if (y < 0)
		y += (-(y / mod) + 1) * mod;
	x %= mod;
	y %= mod;
	x -= 1ll * pow29[r - a] * (s[a] - s[b]);
	y -= 1ll * pow29[a - l] * (s[a] - s[b]); 
	if (x < 0) 
		x += (-(x / mod) + 1) * mod;
	if (y < 0)
		y += (-(y / mod) + 1) * mod;
	x %= mod;
	y %= mod;
//	cout << x << " " << y << endl;
//	cout << l << " " << r << " " << x << " " << y << endl;
	return x == y;
}
int main() {
	cin >> s;
	n = s.size();
	pow29[0] = 1;
	for (int i = 1; i <= n; i++) {
		pow29[i] = pow29[i - 1] * 29;
		pow29[i] %= mod;
	}
	pre[0] = (s[0] - 'a' + 1);
	for (int i = 1; i < n; i++) {
		pre[i] = pre[i - 1] * 29 + (s[i] - 'a' + 1);
		pre[i] %= mod;
	//	cout << i << " " << pre[i] << endl;
	}
	suf[n - 1] = (s[n - 1] - 'a' + 1);
	for (int i = n - 2; i >= 0; i--) {
		suf[i] = suf[i + 1] * 29 + (s[i] - 'a' + 1);
		suf[i] %= mod;
//		cout << i << " " << suf[i] << endl;
	}
//	for (int i = 0; i < n; i++) {
//		for (int j = i; j < n; j++) {
//			cout << i << " " << j << " " << isPal(i, j) << endl;
//		}
//	}
	long long ans = 0;
	int maxi = 0;
	for (int i = 0; i < n; i++) {
		int dw = 0, up = min(i + 1, n - i);
		while (up - dw > 1) {
			int md = (up + dw) / 2;
			if (isPal(i - md, i + md))
				dw = md;
			else
				up = md;
		}
		if (dw > 0) {
			ads[i - dw]++;
			ads[i] += -dw - 1;
			ads[i + 1] += dw;
			adsr[i + dw]++;
			adsr[i] += -dw - 1;
			if (i > 0) 
				adsr[i - 1] += dw;
		}
		d[i - dw]++;
		d[i + up]++;
		ans += up;
//		cout << i << " " << dw << endl;
		if (i - up >= 0 && i + up < n) {
			int ndw = up, nup = min(i + 1, n - 1), a = i - up, b = i + up;
			while (nup - ndw > 1) {
				int nmd = (ndw + nup) / 2;
				if (isPalChng(i - nmd, i + nmd, a, b))
					ndw = nmd;
				else
					nup = nmd;
			}
			
			mp[{i - up, s[i + up]}] += ndw - dw;
			mp[{i + up, s[i - up]}] += ndw - dw;
			v.push_back({i - up, s[i + up]});
			v.push_back({i + up, s[i - up]});
	//		maxi = max(maxi, mp[{i - up, s[i + up]}]);
	//		maxi = max(maxi, mp[{i + up, s[i - up]}]);
		//	maxi = max(maxi, ndw - dw);
	//		cout << ndw << endl;
		}
	}
//	cout << ans << endl;
	for (int i = 1; i < n; i++) {
		int dw = 0, up = min(i + 1, n - i + 1);
		while (up - dw > 1) {
			int md = (up + dw) / 2;
			if (isPal(i - md, i + md - 1))
				dw = md;
			else
				up = md;
		}
		ans += dw;
		if (dw > 0) {
			ads[i - dw]++;
			ads[i] += -dw - 1;
			ads[i + 1] += dw;
			adsr[i + dw - 1]++;
			adsr[i - 1] += -dw - 1;
			if (i > 1)
				adsr[i - 2] += dw;
		}
		d[i - dw]++;
		d[i + dw - 1]--;
//		cout << i << " " << dw << endl;
		if (i - up >= 0 && i + up - 1 < n) {
			int ndw = up, nup = min(i + 1, n - 1 + 1), a = i - up, b = i + up - 1;
			while (nup - ndw > 1) {
				int nmd = (ndw + nup) / 2;
				if (isPalChng(i - nmd, i + nmd - 1, a, b))
					ndw = nmd;
				else
					nup = nmd;
			}

			mp[{i - up, s[i + up - 1]}] += ndw - dw;
			v.push_back({i - up, s[i + up - 1]});
	//		maxi = max(maxi, mp[{i - up, s[i + up - 1]}]);
			mp[{i + up - 1, s[i - up]}] += ndw - dw;
			v.push_back({i + up - 1, s[i - up]});
		//	maxi = max(maxi, mp[{i + up - 1, s[i - up]}]);
		//	maxi = max(maxi, ndw - dw);
//			cout << ndw << endl;
		}
	}
	ps[0] = ads[0];
	for (int i = 1; i < n; i++) {
		ps[i] = ps[i - 1] + ads[i];
	}
	ps2[0] = ps[0];
	for (int i = 1; i < n; i++) {
		ps2[i] = ps2[i - 1] + ps[i];
	}
	for (int i = n - 1; i >= 0; i--)
		psr[i] = psr[i + 1] + adsr[i];
	for (int i = n - 1; i >= 0; i--)
		ps2r[i] = ps2r[i + 1] + psr[i];
//	for (int i = 0; i < n; i++) {
//		cout << ps2[i] << " ";
//	}
//	cout << endl;
//	for (int i = 0; i < n; i++) {
//		cout << ps2r[i] << " ";
//	}
//	cout << endl;
//	cout << ans << " " << maxi << endl;
//	if (n > 100) {
		//ans -= 4;
//	}
//	cout << ans << " " << maxi << endl;
	long long finans = ans;
	for (auto p : v) {
		finans = max(finans, ans + mp[p] - ps2[p.first] - ps2r[p.first]);
	}
//	if (n > 6) {
	//	int x = 0;
	//	n /= x;
//	}
	cout << finans << endl;
	return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:99:6: warning: unused variable 'maxi' [-Wunused-variable]
  int maxi = 0;
      ^~~~

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