Submission #617286

#	Time	Username	Problem	Language	Result	Execution time	Memory
617286		maximath_1	Palinilap (COI16_palinilap)	C++11	100 / 100	116 ms	28680 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
const int MX = 1e5 + 5;
const ll mod = 420691273;
const ll pp = 37;
 
string s, sr;
int n;
ll pwp[MX], ipwp[MX], hsh[MX], hshr[MX];
 
ll pw(ll b, ll e, ll m){
	ll r = 1ll; b %= m;
	for(; e > 0; e /= 2, (b *= b) %= m)
		if(e % 2) (r *= b) %= m;
	return r;
}
 
bool check_palindrome(int lf, int cl, int cr, int rg){
	rg = n - 1 - rg; cr = n - 1 - cr;
	if(lf > cl || rg > cr || lf < 0 || rg < 0) return 0;
 
	ll hashL = hsh[cl] - (lf == 0 ? 0 : hsh[lf - 1]); if(hashL < 0) hashL += mod;
	(hashL *= ipwp[lf]) %= mod;
	ll hashR = hshr[cr] - (rg == 0 ? 0 : hshr[rg - 1]); if(hashR < 0) hashR += mod;
	(hashR *= ipwp[rg]) %= mod;
 
	return (hashL == hashR);
}
 
ll add[MX][30]; // change s[i] to j + 'a', how many palindromes are added
ll delRunning[MX]; ll delCap[MX];
/*
 a  b  c  d  d  c  b  a   |  a  b  c  b  a
 1  2  3  4  4  3  2  1   |  1  2  0  2  1
changing s[i] will delete palindromes according to above
for left side, represent as i - x, x constant (delRuuning = 1, delCap = -x)
for right, represent as x - i, x constant (delRunning = -1, delCap = x)
when added, will become in the form of i * delRunning + delCap
is range update point query, with all queries processed at the end -> offline prefix difference
*/
 
int main(){
	cin >> s;
	sr = s; reverse(sr.begin(),sr.end());
	n = s.size();
 
	pwp[0] = 1;
	for(int i = 1; i < MX; i ++)
		pwp[i] = (pwp[i - 1] * 1ll * pp) % mod;
	ipwp[MX - 1] = pw(pwp[MX - 1], mod - 2, mod);
	for(int i = MX - 2; i >= 0; i --)
		ipwp[i] = (ipwp[i + 1] * 1ll * pp) % mod;
 
	for(int i = 0; i < n; i ++){
		hsh[i] = (pwp[i] * 1ll * (s[i] - 'a')) % mod;
		hshr[i] = (pwp[i] * 1ll * (sr[i] - 'a')) % mod;
 
		if(i > 0){
			hsh[i] += hsh[i - 1]; if(hsh[i] >= mod) hsh[i] -= mod;
			hshr[i] += hshr[i - 1]; if(hshr[i] >= mod) hshr[i] -= mod;
		}
	}
 
	ll base_answer = 0ll;
	for(int cl = 0; cl < n; cl ++){
		for(int cr = cl; cr <= cl + 1; cr ++){
			int lf = 0, rg = min(cl + 1, n - cr), rs = lf;
			for(int md; lf <= rg;){
				md = (lf + rg + 1) / 2;
				if(check_palindrome(cl - md + 1, cl, cr, cr + md - 1)){
					rs = md;
					lf = md + 1;
				}else{
					rg = md - 1;
				}
			}
			base_answer += rs;
 
			// process deleting
			if(cl == cr){
				// odd case
				delRunning[cl - rs + 1] ++; delRunning[cl] --; // left side
				delCap[cl - rs + 1] -= cl - rs; delCap[cl] += cl - rs;
 
				delRunning[cr + 1] --; delRunning[cr + rs] ++; // right side
				delCap[cr + 1] += cr + rs; delCap[cr + rs] -= cr + rs;
			}else{
				// even case
				delRunning[cl - rs + 1] ++; delRunning[cl + 1] --; // left side
				delCap[cl - rs + 1] -= cl - rs; delCap[cl + 1] += cl - rs;
 
				delRunning[cr] --; delRunning[cr + rs] ++; // right side
				delCap[cr] += cr + rs; delCap[cr + rs] -= cr + rs;
			}
 
			// process adding
			int xl = cl - rs, xr = cr + rs; rs ++;
			if(xl < 0 || xr >= n) continue;
			lf = 0, rg = min(cl + 1, n - cr) - rs; rs = lf;
			for(int md; lf <= rg;){
				md = (lf + rg + 1) / 2;
				if(check_palindrome(xl - md, xl - 1, xr + 1, xr + md)){
					rs = md;
					lf = md + 1;
				}else{
					rg = md - 1;
				}
			}
 
			add[xl][s[xr] - 'a'] += rs + 1;
			add[xr][s[xl] - 'a'] += rs + 1;
		}
	}
 
	ll best_change = 0ll;
	ll run = 0ll, cap = 0ll;
	for(int i = 0; i < n; i ++){
		run += delRunning[i];
		cap += delCap[i];
		for(int j = 0; j < 26; j ++) if(s[i] - 'a' != j){
			best_change = max(best_change, add[i][j] - (run * 1ll * i + cap));
		}
	}
 
	cout << base_answer + best_change << endl;
	return 0;
}

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