Submission #138289

#	Time	Username	Problem	Language	Result	Execution time	Memory
138289		Atalasion	Palinilap (COI16_palinilap)	C++14	100 / 100	422 ms	21684 KiB

palinilap

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back

using namespace std;

typedef long long ll;
typedef string str;
typedef pair<ll, ll> pll;

// lines are numbered from 0 to n

const ll N = 1e5 + 10;
const ll H = 727;
const ll MOD = 1e9 + 7;

str s;
ll tav_H[N], pr[N], pl[N], sum_lr[N], sum_rl[N], ans_lr[N], ans_rl[N], p_r[N], p_l[N], p_r2[N], p_l2[N];
ll n;

bool isval(int L, int R, int x){
	int LL = L - x;
	int RR = R + x;
	if (LL < 0 || RR > n) return 0;
	//cout << LL << ' ' << L << ' ' << R << ' ' << RR << '\n';
	ll RH = pr[L] - (pr[LL] * tav_H[L - LL]) % MOD;
	ll LH = pl[R] - (pl[RR] * tav_H[L - LL]) % MOD;
	RH %= MOD;
	RH += MOD;
	RH %= MOD;
	LH %= MOD;
	LH += MOD;
	LH %= MOD;
	return (RH == LH);
}

int BS(int L, int R){
	//if (s[L] != s[R + 1]) return 0;
	int l = 0, r = L + 2;
	while (r - l > 1){
		int mid = (l + r) >> 1;
		if (isval(L, R, mid)) l = mid;
		else r = mid;
	}
	return l;
}

vector<pll> L_P[N], R_P[N];
int main(){
	cin >> s;
	tav_H[0] = 1;
	n = s.size();
	for (int i = 1; i < N; i++) tav_H[i] = tav_H[i - 1] * H % MOD;
	for (int i = 1; i <= n; i++){
		pr[i] = pr[i - 1] * H + s[i - 1] + 3;
		pr[i] %= MOD;
	}
	ll ans = 0;
	for (int i = n - 1; i >= 0; i--){
		pl[i] = pl[i + 1] * H + s[i] + 3;
		pl[i] %= MOD;
	}
	for (int i = 0; i <= n; i++){
		if (i != n){
		//	cout << i << ' ' << i + 1 << ' ';
			int x = BS(i, i + 1);
		//	cout << x << '\n';
			ans += BS(i, i + 1) + 1;
			L_P[i - BS(i, i + 1)].pb({i, i + 1});
			R_P[i + 1 + BS(i, i + 1)].pb({i, i + 1});
			//cout << i << ' ' << i + 1 << ' ' << i - x << ' ' << i << '\n';
			p_r[i - x] --;
			p_r[i] ++;
			p_r2[i] += x;
			p_l[i] ++;
			p_l2[i] += x;
			p_l[i + x] --;
		}
		if (i != 0){
			int x = BS(i, i);
			ans += BS(i, i);
			L_P[i - BS(i, i)].pb({i, i});
			R_P[i + BS(i, i)].pb({i, i});
		//	cout << i << ' ' << i << ' ' << i - x << ' ' << i << '\n';
			p_r[i - x] --;
			p_r2[i] += x;
			p_r[i] ++;
			p_l[i - 1] ++;
			p_l2[i - 1] += x;
			p_l[i + x - 1] --; 
		}		
	}
	ll res = ans;
//	cout << BS(0, 3) << ' ' << BS(1, 3) << '\n';
	//cout << ans << '\n';

	//for (int i = 0; i < n; i++) cout << p_r[i] << '\n';


	for (int i = 1; i <= n; i++) p_r[i] += p_r[i - 1];
	//cout << '\n';
	p_r[0] += p_r2[0];
	for (int i = 1; i <= n; i++) p_r[i] += p_r[i - 1] + p_r2[i];
	//cout << '\n';
	
	for (int i = n; i >= 0; i--) p_l[i] += p_l[i + 1];
	p_l[n] += p_l2[n];
	for (int i = n; i >= 0; i--) p_l[i] += p_l[i + 1] + p_l2[i];
	
//	for (int i = 0; i < n; i++) cout << p_r[i] << ' ';
	//cout << '\n';
	//cout << ans << ' ';
	for (int i = 0; i < s.size(); i++){
		for (int j = 0; j < 26; j++){
			ll ans2 = ans;
			if (j + 'a' == s[i]) continue;
			for (auto u:R_P[i]){
				ll l = u.F - (i - u.S); // khat chap
				if (l == 0) continue;
			//	cout << i << ' ' << u.F << ' ' << u.S << ' ' << l << '\n';
				if (s[l - 1] == j + 'a'){
					ans += BS(l - 1, i + 1);
					ans ++;
				}
			}
			for (auto u:L_P[i + 1]){
				ll r = u.S + u.F - (i + 1);
				if (r == n) continue;
				if (j + 'a' == s[r]){
					ans += BS(i, r + 1);
					ans ++;
				}
			}
			//res = max(res, ans);
			//if (j == 2 && i == 1) cout << ans << '\n';
			ans += p_l[i] + p_r[i];
			res = max(res, ans);
			//if (ans == 10) cout << i << ' ' << j << '\n';
			ans = ans2;
		}
	}
	cout << res;
	

	return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~

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