oj.uz

Submission #617156

# Submission time Handle Problem Language Result Execution time Memory
617156 2022-08-01T09:07:40 Z sentheta Palinilap (COI16_palinilap) C++17
100 / 100
 190 ms 27216 KB 
#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define V vector
#define Int long long
#define rep(i,a,b) for(Int i=(Int)(a); i<(Int)(b); i++)
#define all(x) (x).begin(), (x).end()
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define int long long
#define pii pair<int,int>

const int N = 1e5+5;

const int MOD = 1e9+7;
int SEED, SINV[N];
int bpow(int a,int b){
	int ret = 1;
	while(b){
		if(b&1) ret = ret*a%MOD;
		a = a*a%MOD; b /= 2;
	}
	return ret;
}
int inv(int a){
	return bpow(a, MOD-2);
}

int n;
string s;

// hash of ori string and reversed string
int h[N], rh[N];
int qry(int l,int r){
	int ret = h[r];
	if(l) ret -= h[l-1];
	(ret *= SINV[l] )%=MOD;
	if(ret<0) ret+=MOD;
	return ret;
}
int rqry(int l,int r){
	int ret = rh[l];
	if(r+1<n) ret -= rh[r+1];
	(ret *= SINV[n-1-r] )%=MOD;
	if(ret<0) ret+=MOD;
	return ret;
}


// add arithmetic sequence to range
// point query
int loss[N];
#define mid ((tl+tr)/2)
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Segtree{
	int lzl[2*N], lzr[2*N];
	void upd(int l,int r,int addl,int addr,int v=0,int tl=0,int tr=n-1){
		// int a = addl, b = (r-l==0 ? 0:(addr-addl)/(r-l));
		// rep(i,l,r+1) loss[i] += a + (i-l)*b;
		// return;
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			int a = addl, b = (r-l==0 ? 0:(addr-addl)/(r-l));
			addl = a + (tl-l)*b;
			addr = a + (tr-l)*b;
			
			lzl[v] += addl; lzr[v] += addr;

			return;
		}
		upd(l,r,addl,addr, lc,tl,mid);
		upd(l,r,addl,addr, rc,mid+1,tr);
	}
	void build_loss(int v=0,int tl=0,int tr=n-1){
		// return;
		if(tl==tr){
			// dbg(st[v]);
			loss[tl] = lzl[v];
			return;
		}
		if(lzl[v] || lzr[v]){
			upd(tl,tr,lzl[v],lzr[v], lc,tl,mid);
			upd(tl,tr,lzl[v],lzr[v], rc,mid+1,tr);
			lzl[v] = lzr[v] = 0;
		}
		build_loss(lc,tl,mid);
		build_loss(rc,mid+1,tr);
	}
} segtree;

// find longest [tl..l] == rev([r..tr]);
int f(int l,int r){
	if(l<0 || r<0 || n<=l || n<=r) return 0;
	// int i=l, j=r;
	// while(0<=i && j<n && s[i]==s[j]) i--,j++;
	// return l-i;

	int len = 0;
	for(int J=1<<20; J; J/=2)
		if(len+J<=n && l-len-J+1>=0 && r+len+J-1<n &&
			qry(l-len-J+1,l)==rqry(r,r+len+J-1)) len+=J;
	return len;
}

int gains[N][26];

int count_pali(){
	int mul = 1;
	rep(i,0,n){
		h[i] = 0;
		if(i) h[i] = h[i-1];
		(h[i] += mul*s[i] )%=MOD;
		(mul *= SEED )%=MOD;
	}
	mul = 1;
	for(int i=n-1; i>=0; i--){
		rh[i] = 0;
		if(i+1<n) rh[i] = rh[i+1];
		(rh[i] += mul*s[i] )%=MOD;
		(mul *= SEED )%=MOD;
	}

	int ret = 0;

	// even length palindrome
	rep(i,1,n){
		// [l..i-1] == rev([i..r])
		int len = f(i-1,i);
		ret += len;
	}

	// odd length palindrome
	rep(i,0,n){
		// [l..i] == rev([i..r])
		int len = f(i,i);
		ret += len;
	}
	return ret;
}

int ans = 0;

signed main(){
	srand(time(0));
	SEED = rand()%MOD;
	// SEED = 3;
	SINV[0] = 1; SINV[1] = inv(SEED);
	rep(i,2,N){
		(SINV[i] = SINV[i-1]*SINV[1] )%=MOD;
	}
	assert(SEED*SINV[1]%MOD==1);

	cin >> s;
	n = s.size();

	// ans = 0;
	// rep(i,0,n) for(char c='a'; c<='z'; c++){
	// 	swap(s[i], c);
	// 	ans = max(ans, count_pali());
	// 	swap(s[i], c);
	// }
	// int correct = ans;
	// ans = 0;

	// cout << ans << nl; return 0;


	int mul = 1;
	rep(i,0,n){
		h[i] = 0;
		if(i) h[i] = h[i-1];
		(h[i] += mul*s[i] )%=MOD;
		(mul *= SEED )%=MOD;
	}
	mul = 1;
	for(int i=n-1; i>=0; i--){
		rh[i] = 0;
		if(i+1<n) rh[i] = rh[i+1];
		(rh[i] += mul*s[i] )%=MOD;
		(mul *= SEED )%=MOD;
	}


	// even length palindrome
	rep(i,1,n){
		// [l..i-1] == rev([i..r])
		int len = f(i-1,i);
		int l = i-len, r = i+len-1;

		// dbg(i); dbg(len); dbg(l); dbg(r);
		// cout << nl;

		ans += len;
		if(l<=i-1) segtree.upd(l,i-1, 1,len);
		if(i<=r) segtree.upd(i,r, len,1);

		// if char were changed
		if(0<=l-1 && r+1<n){
			assert(s[l-1]!=s[r+1]);
			int tlen = f(l-2,r+2)+1;
			// dbg(tlen);

			gains[l-1][s[r+1]-'a'] += tlen;
			gains[r+1][s[l-1]-'a'] += tlen;
		}
		// cout << nl;
	}
	// cout << "##########" << nl;


	// odd length palindrome
	rep(i,0,n){
		// [l..i] == rev([i..r])
		int len = f(i,i);
		int l = i-len+1, r = i+len-1;

		// dbg(i); dbg(len);
		// dbg(l); dbg(r);
		// cout << nl;

		ans += len;
		// segtree.upd(i,i, len-1,len-1);
		if(l<=i-1) segtree.upd(l,i-1, 1,len-1);
		if(i+1<=r) segtree.upd(i+1,r, len-1,1);

		// if char were changed
		if(0<=l-1 && r+1<n){
			// assert(s[l-1]!=s[r+1]);
			int tlen = f(l-2,r+2)+1;
			// dbg(tlen);
			gains[l-1][s[r+1]-'a'] += tlen;
			gains[r+1][s[l-1]-'a'] += tlen;
		}
	}


	// dbg(ans);
	segtree.build_loss();
	// rep(i,0,n) dbg(loss[i]);

	// get answer
	int maxdelta = 0;
	rep(i,0,n) rep(c,0,26){
		int delta = gains[i][c] - loss[i];

		// if(delta > maxdelta){
		// 	dbg(i); dbg((char)(c+'a'));
		// 	dbg(gains[i][c]); dbg(loss[i]);
		// }
		maxdelta = max(maxdelta, delta);
	}
	ans += maxdelta;
	// dbg(s); dbg(correct); dbg(ans);
	// assert(correct==ans);

	cout << ans << nl;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2380 KB Output is correct
2 Correct 7 ms 2372 KB Output is correct
3 Correct 6 ms 2368 KB Output is correct
4 Correct 5 ms 1884 KB Output is correct
5 Correct 6 ms 2132 KB Output is correct
6 Correct 6 ms 2388 KB Output is correct
7 Correct 6 ms 2388 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 27084 KB Output is correct
2 Correct 190 ms 27144 KB Output is correct
3 Correct 165 ms 27212 KB Output is correct
4 Correct 131 ms 27092 KB Output is correct
5 Correct 118 ms 27208 KB Output is correct
6 Correct 115 ms 27104 KB Output is correct
7 Correct 112 ms 27204 KB Output is correct
8 Correct 139 ms 6856 KB Output is correct
9 Correct 143 ms 27148 KB Output is correct
10 Correct 118 ms 27120 KB Output is correct
11 Correct 170 ms 27172 KB Output is correct
12 Correct 181 ms 27204 KB Output is correct
13 Correct 137 ms 27204 KB Output is correct
14 Correct 113 ms 27188 KB Output is correct
15 Correct 122 ms 27200 KB Output is correct
16 Correct 173 ms 27216 KB Output is correct
17 Correct 93 ms 27212 KB Output is correct
18 Correct 119 ms 27176 KB Output is correct
19 Correct 96 ms 27204 KB Output is correct