Submission #374173

#	Time	Username	Problem	Language	Result	Execution time	Memory
374173		srvlt	Palinilap (COI16_palinilap)	C++17	0 / 100	166 ms	25068 KiB

palinilap

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mem(x, y) memset(& x, y, sizeof(x))
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
using namespace std;

const int n0=1e5+123;
int n;
string s;
namespace Hash {
	const array<int,2> mod={(int)1e9+7,(int)1e9+9};
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	int base=uniform_int_distribution<int>(27,(int)1e9)(rng);
	struct mint {
		array<int,2> x;
		mint(int val=0) {
			x[0]=x[1]=val;
		}
		void operator *= (const mint &a) {
			x[0]=(ll)x[0]*a.x[0]%mod[0];
			x[1]=(ll)x[1]*a.x[1]%mod[1];
		}
		void operator += (const mint &a) {
			x[0]+=a.x[0];if(x[0]>=mod[0]) x[0]-=mod[0];
			x[1]+=a.x[1];if(x[1]>=mod[1]) x[1]-=mod[1];
		}
		void operator -= (const mint &a) {
			x[0]-=a.x[0];if(x[0]<0) x[0]+=mod[0];
			x[1]-=a.x[1];if(x[1]<0) x[1]+=mod[1];
		}
		mint operator * (const mint &a) {
			mint res=*this;
			res*=a;
			return res;
		}
		mint operator + (const mint &a) {
			mint res=*this;
			res+=a;
			return res;
		}
		mint operator - (const mint &a) {
			mint res=*this;
			res-=a;
			return res;
		}
		bool operator == (const mint &a) {
			return x[0]==a.x[0] && x[1]==a.x[1];
		}
	};
	mint pref[n0],suf[n0],pw[n0];
	void build() {
		pw[0]=1;
		for(int i=1; i<=n; i++) {
			pw[i]=pw[i-1]*base;
			pref[i]=pref[i-1]+pw[i]*(s[i-1]-'a'+1);
		}
		for(int i=n; i>=1; i--) {
			suf[i]=suf[i+1]+pw[n-i+1]*(s[i-1]-'a'+1);
		}
	};
	mint get(int l,int r) {
		return pw[n-r]*(pref[r]-pref[l-1]);
	}
	mint get_rev(int l,int r) {
		return pw[l-1]*(suf[l]-suf[r+1]);
	}
}
bool pal(int l,int r,int l2,int r2) {
	if(l<1 || l2<1 || r>n || r2>n) return 0;
	return Hash::get(l,r)==Hash::get_rev(l2,r2);
}
int find(int L,int R) {
	int l=-1,r=n;
	while(l<r-1) {
		int mid=l+r>>1;
		if(pal(L-mid,L,R,R+mid)) l=mid;
		else r=mid;
	}
	return l;
}
ll mul[n0],add[n0];
void add_inc(int l,int r,int x) {
	//(x-l)+i
	add[l]+=x-l,add[r+1]-=x-l;
	mul[l]++,mul[r+1]--;
}
void add_dec(int l,int r,int x) {
	//(x+l)-i
	add[l]+=x+l,add[r+1]-=x+l;
	mul[l]--,mul[r+1]++;
}
ll get(int pos) {
	return add[pos]+mul[pos]*pos;
}
ll positive[n0][26],init;
void process(int L,int R) {
	int a=find(L,R);
	init+=a+1;
	int b=find(L-a-2,R+a+2);
	if(L-a-1>=1 && R+a+1<=n) {
		positive[L-a-1][s[R+a]-'a']+=1+(b+1);
		positive[R+a+1][s[L-a-2]-'a']+=1+(b+1);
	}
	if(a>=0) {
		add_inc(L-a,L,-a-1);
		add_dec(R,R+a,-1);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> s;n=SZ(s);
	Hash::build();
	for(int i=1; i<=n-1; i++) process(i,i+1);
	for(int i=1; i<=n-2; i++) process(i,i+2);
	ll ans=init;
	for(int i=1; i<=n; i++) {
		add[i]+=add[i-1];
		mul[i]+=mul[i-1];
		ll diff=get(i);
		ll cur=0;
		for(int j=0; j<26; j++) {
			cur=0;
			if(s[i-1]-'a'!=j) cur+=diff;
			cur+=positive[i][j];
			ans=max(ans,init+cur);
		}
	}
	cout << ans+n;
}

Compilation message (stderr)

palinilap.cpp: In function 'int find(int, int)':
palinilap.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int mid=l+r>>1;
      |           ~^~

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