oj.uz

답안 #138289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138289 2019-07-29T16:51:50 Z Atalasion Palinilap (COI16_palinilap) C++14
100 / 100
 422 ms 21684 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back

using namespace std;

typedef long long ll;
typedef string str;
typedef pair<ll, ll> pll;

// lines are numbered from 0 to n

const ll N = 1e5 + 10;
const ll H = 727;
const ll MOD = 1e9 + 7;

str s;
ll tav_H[N], pr[N], pl[N], sum_lr[N], sum_rl[N], ans_lr[N], ans_rl[N], p_r[N], p_l[N], p_r2[N], p_l2[N];
ll n;

bool isval(int L, int R, int x){
	int LL = L - x;
	int RR = R + x;
	if (LL < 0 || RR > n) return 0;
	//cout << LL << ' ' << L << ' ' << R << ' ' << RR << '\n';
	ll RH = pr[L] - (pr[LL] * tav_H[L - LL]) % MOD;
	ll LH = pl[R] - (pl[RR] * tav_H[L - LL]) % MOD;
	RH %= MOD;
	RH += MOD;
	RH %= MOD;
	LH %= MOD;
	LH += MOD;
	LH %= MOD;
	return (RH == LH);
}

int BS(int L, int R){
	//if (s[L] != s[R + 1]) return 0;
	int l = 0, r = L + 2;
	while (r - l > 1){
		int mid = (l + r) >> 1;
		if (isval(L, R, mid)) l = mid;
		else r = mid;
	}
	return l;
}

vector<pll> L_P[N], R_P[N];
int main(){
	cin >> s;
	tav_H[0] = 1;
	n = s.size();
	for (int i = 1; i < N; i++) tav_H[i] = tav_H[i - 1] * H % MOD;
	for (int i = 1; i <= n; i++){
		pr[i] = pr[i - 1] * H + s[i - 1] + 3;
		pr[i] %= MOD;
	}
	ll ans = 0;
	for (int i = n - 1; i >= 0; i--){
		pl[i] = pl[i + 1] * H + s[i] + 3;
		pl[i] %= MOD;
	}
	for (int i = 0; i <= n; i++){
		if (i != n){
		//	cout << i << ' ' << i + 1 << ' ';
			int x = BS(i, i + 1);
		//	cout << x << '\n';
			ans += BS(i, i + 1) + 1;
			L_P[i - BS(i, i + 1)].pb({i, i + 1});
			R_P[i + 1 + BS(i, i + 1)].pb({i, i + 1});
			//cout << i << ' ' << i + 1 << ' ' << i - x << ' ' << i << '\n';
			p_r[i - x] --;
			p_r[i] ++;
			p_r2[i] += x;
			p_l[i] ++;
			p_l2[i] += x;
			p_l[i + x] --;
		}
		if (i != 0){
			int x = BS(i, i);
			ans += BS(i, i);
			L_P[i - BS(i, i)].pb({i, i});
			R_P[i + BS(i, i)].pb({i, i});
		//	cout << i << ' ' << i << ' ' << i - x << ' ' << i << '\n';
			p_r[i - x] --;
			p_r2[i] += x;
			p_r[i] ++;
			p_l[i - 1] ++;
			p_l2[i - 1] += x;
			p_l[i + x - 1] --; 
		}		
	}
	ll res = ans;
//	cout << BS(0, 3) << ' ' << BS(1, 3) << '\n';
	//cout << ans << '\n';

	//for (int i = 0; i < n; i++) cout << p_r[i] << '\n';


	for (int i = 1; i <= n; i++) p_r[i] += p_r[i - 1];
	//cout << '\n';
	p_r[0] += p_r2[0];
	for (int i = 1; i <= n; i++) p_r[i] += p_r[i - 1] + p_r2[i];
	//cout << '\n';
	
	for (int i = n; i >= 0; i--) p_l[i] += p_l[i + 1];
	p_l[n] += p_l2[n];
	for (int i = n; i >= 0; i--) p_l[i] += p_l[i + 1] + p_l2[i];
	
//	for (int i = 0; i < n; i++) cout << p_r[i] << ' ';
	//cout << '\n';
	//cout << ans << ' ';
	for (int i = 0; i < s.size(); i++){
		for (int j = 0; j < 26; j++){
			ll ans2 = ans;
			if (j + 'a' == s[i]) continue;
			for (auto u:R_P[i]){
				ll l = u.F - (i - u.S); // khat chap
				if (l == 0) continue;
			//	cout << i << ' ' << u.F << ' ' << u.S << ' ' << l << '\n';
				if (s[l - 1] == j + 'a'){
					ans += BS(l - 1, i + 1);
					ans ++;
				}
			}
			for (auto u:L_P[i + 1]){
				ll r = u.S + u.F - (i + 1);
				if (r == n) continue;
				if (j + 'a' == s[r]){
					ans += BS(i, r + 1);
					ans ++;
				}
			}
			//res = max(res, ans);
			//if (j == 2 && i == 1) cout << ans << '\n';
			ans += p_l[i] + p_r[i];
			res = max(res, ans);
			//if (ans == 10) cout << i << ' ' << j << '\n';
			ans = ans2;
		}
	}
	cout << res;
	

	return 0;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 8 ms 5880 KB Output is correct
3 Correct 8 ms 5880 KB Output is correct
4 Correct 8 ms 5880 KB Output is correct
5 Correct 8 ms 5852 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 6520 KB Output is correct
2 Correct 17 ms 6520 KB Output is correct
3 Correct 21 ms 6652 KB Output is correct
4 Correct 16 ms 6392 KB Output is correct
5 Correct 19 ms 6392 KB Output is correct
6 Correct 22 ms 6520 KB Output is correct
7 Correct 21 ms 6520 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 408 ms 20872 KB Output is correct
2 Correct 256 ms 20196 KB Output is correct
3 Correct 238 ms 20080 KB Output is correct
4 Correct 385 ms 20872 KB Output is correct
5 Correct 384 ms 20908 KB Output is correct
6 Correct 382 ms 20856 KB Output is correct
7 Correct 386 ms 20944 KB Output is correct
8 Correct 184 ms 20112 KB Output is correct
9 Correct 391 ms 20868 KB Output is correct
10 Correct 395 ms 20872 KB Output is correct
11 Correct 239 ms 20068 KB Output is correct
12 Correct 364 ms 21684 KB Output is correct
13 Correct 376 ms 20544 KB Output is correct
14 Correct 422 ms 20728 KB Output is correct
15 Correct 387 ms 20728 KB Output is correct
16 Correct 274 ms 20160 KB Output is correct
17 Correct 377 ms 20364 KB Output is correct
18 Correct 400 ms 20344 KB Output is correct
19 Correct 377 ms 20344 KB Output is correct