oj.uz

답안 #140594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140594 2019-08-03T16:20:19 Z aarr Palinilap (COI16_palinilap) C++14
100 / 100
 446 ms 35088 KB 
#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

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

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1144 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 13 ms 1396 KB Output is correct
4 Correct 9 ms 1196 KB Output is correct
5 Correct 12 ms 1404 KB Output is correct
6 Correct 13 ms 1524 KB Output is correct
7 Correct 15 ms 2036 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 17640 KB Output is correct
2 Correct 341 ms 17884 KB Output is correct
3 Correct 184 ms 16360 KB Output is correct
4 Correct 341 ms 23020 KB Output is correct
5 Correct 345 ms 23276 KB Output is correct
6 Correct 340 ms 23156 KB Output is correct
7 Correct 342 ms 23180 KB Output is correct
8 Correct 96 ms 8452 KB Output is correct
9 Correct 358 ms 23132 KB Output is correct
10 Correct 333 ms 23000 KB Output is correct
11 Correct 339 ms 17844 KB Output is correct
12 Correct 308 ms 17816 KB Output is correct
13 Correct 351 ms 18592 KB Output is correct
14 Correct 339 ms 24680 KB Output is correct
15 Correct 334 ms 23428 KB Output is correct
16 Correct 379 ms 24080 KB Output is correct
17 Correct 446 ms 35024 KB Output is correct
18 Correct 385 ms 17756 KB Output is correct
19 Correct 423 ms 35088 KB Output is correct