oj.uz

Submission #138874

# Submission time Handle Problem Language Result Execution time Memory
138874 2019-07-30T16:28:46 Z alishahali1382 Palinilap (COI16_palinilap) C++14
100 / 100
 121 ms 24384 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, B=10007;

ll n, m, k, u, v, x, y, t, a, b, ans, pal;
char A[MAXN];
ll hl[MAXN], hr[MAXN], tav[MAXN];
ll ps1[MAXN];
ll cnt[MAXN][26];

ll getl(int l, int r){
	ll res=(hl[r]-hl[l-1]*tav[r-l+1])%mod;
	return (res+mod)%mod;
}

ll getr(int l, int r){
	ll res=(hr[l]-hr[r+1]*tav[r-l+1])%mod;
	return (res+mod)%mod;
}

bool check(int l1, int r1, int l2, int r2){
	if (min(l1, l2)<1 || n<max(r1, r2)) return 0;
	//debug("shit")
	return getl(l1, r1)==getr(l2, r2);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string s;
	cin>>s;
	n=s.size();
	for (int i=1; i<=n; i++) A[i]=s[i-1];
	for (int i=1; i<=n; i++) hl[i]=(hl[i-1]*B+A[i])%mod;
	for (int i=n; i; i--) hr[i]=(hr[i+1]*B+A[i])%mod;
	tav[0]=1;
	for (int i=1; i<=n; i++) tav[i]=tav[i-1]*B%mod;
	
	/*
	// ---------------------------------------------------
	
	for (int i=0; i<=n; i++) cerr<<hl[i]<<" \n"[i==n];

	debug(check(1, 1, 2, 2))
	debug(getl(1, 1))
	debug(getl(2, 2))
	*/
	
	/// even lenth
	for (int i=1; i<=n; i++){
		int dwn=0, up=n+1;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(i-mid+1, i, i+1, i+mid)) dwn=mid;
			else up=mid;
		}
		int len=dwn, l=i-len+1, r=i+len;
		
		//debug2(i, len)
		if (len){ 	
		ps1[l]++;
		ps1[i+1]--;
		ps1[i+2]--;
		ps1[r+2]++;
		//debug2(l, r)
		}
		// tof can be deleted		

		pal+=len;
		if (l<=1 || r>=n) continue ;
		
		dwn=0, up=n;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(l-1-mid, l-2, r+2, r+1+mid)) dwn=mid;
			else up=mid;
		}
		cnt[l-1][A[r+1]-'a']+=dwn+1;
		cnt[r+1][A[l-1]-'a']+=dwn+1;
	}
	
	
	// odd lenth
	for (int i=1; i<=n; i++){
		int dwn=0, up=n+1;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(i-mid, i-1, i+1, i+mid)) dwn=mid;
			else up=mid;
		}
		int len=dwn, l=i-len, r=i+len;

		//debug2(i, len)

		ps1[l]++;
		ps1[i]-=len+1;
		ps1[i+1]+=len*2;
		ps1[i+2]-=len+1;
		ps1[r+2]++;

		pal+=len+1;
		if (l<=1 || r>=n) continue ;
		
		dwn=0, up=n;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(l-1-mid, l-2, r+2, r+1+mid)) dwn=mid;
			else up=mid;
		}
		cnt[l-1][A[r+1]-'a']+=dwn+1;
		cnt[r+1][A[l-1]-'a']+=dwn+1;
	}
	// ----------
	
	

	for (int i=1; i<=n; i++) ps1[i]+=ps1[i-1];
	for (int i=1; i<=n; i++) ps1[i]+=ps1[i-1];
	//for (int i=1; i<=n; i++) cerr<<ps1[i]<<" \n"[i==n];

	ans=pal;
	for (int i=1; i<=n; i++) for (int c=0; c<26; c++) ans=max(ans, pal-ps1[i]+cnt[i][c]);
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Correct 5 ms 1532 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 5 ms 1404 KB Output is correct
6 Correct 6 ms 1528 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 24212 KB Output is correct
2 Correct 86 ms 24184 KB Output is correct
3 Correct 79 ms 24312 KB Output is correct
4 Correct 107 ms 24284 KB Output is correct
5 Correct 107 ms 24184 KB Output is correct
6 Correct 117 ms 24232 KB Output is correct
7 Correct 121 ms 24312 KB Output is correct
8 Correct 46 ms 3964 KB Output is correct
9 Correct 109 ms 24312 KB Output is correct
10 Correct 107 ms 24384 KB Output is correct
11 Correct 85 ms 24312 KB Output is correct
12 Correct 112 ms 24320 KB Output is correct
13 Correct 117 ms 24312 KB Output is correct
14 Correct 109 ms 24312 KB Output is correct
15 Correct 105 ms 24280 KB Output is correct
16 Correct 100 ms 24316 KB Output is correct
17 Correct 100 ms 24280 KB Output is correct
18 Correct 109 ms 24312 KB Output is correct
19 Correct 100 ms 24312 KB Output is correct