제출 #248393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248393		vanic	Palinilap (COI16_palinilap)	C++14	100 / 100	125 ms	26232 KiB

palinilap

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;

typedef long long ll;
const int maxn=1e5+5, p=29, mod=1e9+7;

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	else if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}

inline int mul(int a, int b){
	return (ll)a*b%mod;
}


int pref[maxn], suff[maxn];
int n;
string s;
int pot[maxn];
ll sw[maxn];
ll oduz[maxn];
ll dodaj[maxn][p];
ll sol;


void precompute(){
	pot[0]=1;
	for(int i=1; i<maxn; i++){
		pot[i]=mul(pot[i-1], p);
	}
}

bool provjeri(int x, int y, int kolko){
	return sum(pref[x+1], -mul(pref[x-kolko], pot[kolko+1]))==sum(suff[n-y], -mul(suff[n-y-kolko-1], pot[kolko+1]));
}

int binary(int x, int y){
	int lo=0, hi=min(x+1, n-y), mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(provjeri(x, y, mid)){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo;
}

void rijesi(int x, bool p){
	int l, d;
	if(p){
		l=x;
		d=x+1;
	}
	else{
		l=x-1;
		d=x+1;
	}
	int val;
	if(l<0 || d>=n){
		val=0;
	}
	else{
		val=binary(l, d);
	}
	l-=val;
	d+=val;
	sol+=x-l;
//	cout << x << " " << p << " " << x-l << endl;
//	cout << x << " " << p << " " << l << " " << d << '\n';
	if(p){
		sw[l+1]++;
		sw[x+1]--;
		sw[x+2]--;
		sw[d+1]++;
	}
	else{
		sw[l+1]++;
		sw[x+1]-=2;
		sw[d+1]++;
		oduz[x]+=x-l;
	}
}

void rijesi2(int x, bool p){
	int l, d;
	if(p){
		l=x;
		d=x+1;
	}
	else{
		l=x-1;
		d=x+1;
	}
	if(l<0 || d>=n){
		return;
	}
	int val;
	val=binary(l, d);
	l-=val;
	d+=val;
	if(l<0 || d>=n){
		return;
	}
	dodaj[l][s[d]-'a']++;
	dodaj[d][s[l]-'a']++;
	if(l-1<0 || d+1>=n){
		return;
	}
	val=binary(l-1, d+1);
	dodaj[l][s[d]-'a']+=val;
	dodaj[d][s[l]-'a']+=val;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	precompute();
	cin >> s;
	n=s.size();
	for(int i=0; i<n; i++){
		pref[i+1]=sum(mul(pref[i], p), s[i]-'a');
		suff[i+1]=sum(mul(suff[i], p), s[n-i-1]-'a');
	}
	for(int i=0; i<n; i++){
		rijesi(i, 0);
		rijesi(i, 1);
	}
	ll val=0;
	ll upd=0;
	for(int i=0; i<n; i++){
		upd+=sw[i];
		val-=upd;
		oduz[i]+=val;
	}
/*	for(int i=0; i<n; i++){
		cout << oduz[i] << " ";
	}
	cout << '\n';*/
	for(int i=0; i<n; i++){
		rijesi2(i, 0);
		rijesi2(i, 1);
	}
	ll maksi=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<p; j++){
			maksi=max(maksi, oduz[i]+dodaj[i][j]);
		}
	}
	cout << sol+maksi << '\n';
	return 0;
}

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