Submission #895229

#	Time	Username	Problem	Language	Result	Execution time	Memory
895229		vjudge1	Palinilap (COI16_palinilap)	C++17	100 / 100	236 ms	41192 KiB

palinilap

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10, M = 26 + 10;
const ll mod = 1e9 + 7;

ll um(ll a, ll b){
	return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll add(ll a, ll b){
	return ((1LL * a + b) % mod + mod) % mod;
}
ll p = 293, pr[N];
ll arr[N][M], x[N], hs1[N], hs2[N], n;
ll get(ll l1, ll r1, ll l2, ll r2){
	ll s1 = hs1[r1], s2 = subr(hs2[r2], hs2[l2 + 1]);
	if(l1 != 0) s1 = subr(s1, hs1[l1 - 1]);
	if(l1 >= n - l2 - 1) s2 = um(s2, pr[l1 - (n - l2 - 1)]);
	else s1 = um(s1, pr[n - l2 - 1 - l1]);
	
	if(s1 == s2) return true;
	return false;
}
ll in[N], out[N], incnt[N], outcnt[N];
ll getr(ll from, ll to){
	ll l = 0, r = min(n - to, from + 1);
	while(r - l > 1){
		ll mid = (r + l) / 2;
		if(get(to, to + mid, from, from - mid)) l = mid;
		else r = mid;
	}
	if(x[from] != x[to]) r = 0;
	return r;
}
void calc(ll from, ll to){
	ll r = getr(from, to);
	if(from - r >= 0 && to + r < n){
		from = from - r - 1;
		to = to + r + 1;
		if(from < 0 || to >= n){
			from++;
			to--;
			arr[from][x[to]]++;
			arr[to][x[from]]++;
			return;
		}
		ll lx = 0, rx = min(from + 1, n - to), cm = 1;
		while(rx - lx > 1){
			ll mid = (rx + lx) / 2;
			if(get(to, to + mid, from, from - mid)) lx = mid;
			else rx = mid;
		}
		if(get(to, to + lx, from, from - lx) == true) cm = lx + 2;
		from++;
		to--;
		arr[from][x[to]] += cm;
		arr[to][x[from]] += cm;
	}
}
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	string s;
  	cin >> s;
  	n = (ll)s.size();
  	// build
  	pr[0] = 1LL;
  	for(ll i = 1; i <= n; i++){
  		pr[i] = um(pr[i - 1], p);
  	}
	for(ll i = 0; i < n; i++){
		x[i] = s[i] - 'a';
		if(i == 0) hs1[i] = x[i];
		else hs1[i] = add(hs1[i - 1], um(x[i], pr[i]));
	}
	for(ll i = n - 1; i >= 0; i--){
		hs2[i] = add(hs2[i + 1], um(x[i], pr[n - i - 1]));
	}
	
	// take answer
  	for(ll i = 0; i < n; i++){
  		ll r = getr(i, i);
  		in[i] += r;
  		incnt[i]++;
  		incnt[i + r]--;
  		
  		arr[i][x[i]] -= r;
  		
  		out[i] += r;
  		outcnt[i]++;
  		if(i - r >= 0) outcnt[i - r]--;
  		
  		r = getr(i, i + 1);
  		if(r == 0 || x[i] != x[i + 1]) continue;
  		in[i + 1] += r;
  		incnt[i + 1]++;
  		incnt[i + 1 + r]--;
  		
  		out[i] += r;
  		outcnt[i]++;
  		if(i - r >= 0) outcnt[i - r]--;
  	}
  	ll cur = 0, c = 0, ans = 0;
  	for(ll i = 0; i < n; i++){
  		cur += in[i];
  		c += incnt[i];
  		arr[i][x[i]] += cur;
  		cur -= c;
  	}
  	cur = c = 0;
  	for(ll i = n - 1; i >= 0; i--){
  		cur += out[i];
  		c += outcnt[i];
  		arr[i][x[i]] += cur;
  		cur -= c;
  		
  		ans += arr[i][x[i]];
  	}
  	// for(ll i = 0; i < n; i++){
  		// cout << arr[i][x[i]] << " ";
  	// }
  	// cout << endl;
  	cur = ans;
  	for(ll i = 0; i < n; i++){
  		calc(i, i);
  		calc(i, i + 1);
  	}
  	ll f1 = -1, f2 = -1;
  	for(ll i = 0; i < n; i++){
  		for(ll j = 0; j < 26; j++){
  			if(j == x[i]) continue;
  			if(cur + arr[i][j] - arr[i][x[i]] + 1 >= ans){
  				ans = max(ans, cur + arr[i][j] - arr[i][x[i]] + 1);
  				f1 = i;
  				f2 = j;
  			}
  		}
  	}
  	if(f1 != -1) x[f1] = f2;
  	for(ll i = 0; i < n; i++){
		if(i == 0) hs1[i] = x[i];
		else hs1[i] = add(hs1[i - 1], um(x[i], pr[i]));
	}
	for(ll i = n - 1; i >= 0; i--){
		hs2[i] = add(hs2[i + 1], um(x[i], pr[n - i - 1]));
	}
  	ll real = 0;
  	for(ll i = 0; i < n; i++){
  		real += getr(i, i);
  		real += getr(i, i + 1);
  	}
  	cout << real;
  return 0;
}

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