oj.uz

Submission #247638

# Submission time Handle Problem Language Result Execution time Memory
247638 2020-07-11T18:54:30 Z emaborevkovic Palinilap (COI16_palinilap) C++14
100 / 100
 63 ms 25720 KB 
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define pb push_back

const int N = 1e5+11;
const ll baza = 37, MOD = 1e9+7;
string s;
int n;
ll hf[N], hb[N]; 
pair <ll, ll> sweep[N];
ll p[26][N];
ll suma;
ll pot[N];
ll mns[N];

ll add (ll a, ll b) {
	ll ret = a+b;
	if (ret > MOD) ret -= MOD;
	if (ret < 0) ret += MOD;
	return ret;
}

ll mult (ll a, ll b) {
	ll ret = a*b;
	ret %= MOD;
	if (ret < 0) ret += MOD;
	return ret;
}

void hashiranje() {
	hf[0] = (s[0] - 'a' + 1);
	ll mno = baza;
	for (int i=1;i<n;i++) {
		hf[i] = mult (s[i] - 'a' + 1, mno);
		mno = mult(baza, mno);
		hf[i] = add (hf[i], hf[i-1]);
	}
	/////////////////////////////////////////////////
	hb[n-1] = (s[n-1] - 'a' + 1);
	mno = baza;
	for (int i=n-2;i>=0;i--) {
		hb[i] = mult(s[i] - 'a' + 1, mno);
		mno = mult(baza, mno);
		hb[i] = add (hb[i], hb[i+1]);
	}
}

bool jesu (int x1, int y1, int x2, int y2) {
	ll prvi = hf[y1];
	if (x1 > 0) prvi = add(prvi, -hf[x1-1]);
	ll drugi = hb[x2];
	if (y2 < n-1) drugi = add(drugi, -hb[y2+1]);
	int mno1 = y1;
	int mno2 = n-1-x2;
	if (mno1 > mno2) drugi = mult(drugi, pot[mno1-mno2]);
	else prvi = mult(prvi, pot[mno2-mno1]);
	if (prvi == drugi) return 1;
	else return 0;
}

int isti (int x, int y) {
	if (x < 0 || y > n-1) return 0;
	if (s[x] != s[y]) return 0;
	int lo = 0;
	int hi = min(x, n-1-y);
	while (lo < hi) {
		int mid = (lo+hi)/2+1;
		if (jesu(x-mid, x, y, y+mid)) lo = mid;
		else hi = mid-1;
	}
	return lo+1;
}

bool palin (int x, int y) {
	return jesu(x, y, x, y);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	n = s.size();
	hashiranje();
	pot[0] = 1;
	for (int i=1;i<n;i++) pot[i] = mult(pot[i-1], baza);
	for (int i=0;i<n;i++) {
		int lo = 0;
		int hi = min(i, n-1-i);
		while (lo < hi) {
			int mid = (lo+hi)/2+1;
			if (palin(i-mid, i+mid)) lo = mid;
			else hi = mid-1;
		}
		int r = lo;
		sweep[i-r].ff += 1;
		sweep[i].ff += -1;
		sweep[i].ss += -r;
		if (r > 0) {
			sweep[i+1].ff -= 1;
			sweep[i+1].ss += r+1;
			if (i+r+1 < n) {
				sweep[i+r+1].ff += 1;
				sweep[i+r+1].ss += -1;
			}
		}
		suma += r+1;
		if (i-r-1 < 0 || i+r+1 > n-1) continue;
		int sada = isti(i-r-2, i+r+2);
		p[s[i+r+1] - 'a'][i-r-1] += sada+1;
		p[s[i-r-1] - 'a'][i+r+1] += sada+1;
	}
	/////////////////////////////////////////////////////////////
	for (int i=0;i<n-1;i++) {
		if (s[i] != s[i+1]) {
			int sada = isti(i-1, i+2);
			p[s[i+1]-'a'][i] += sada+1;
			p[s[i]-'a'][i+1] += sada+1;
			continue;
		}
		int lo = 0;
		int hi = min(i, n-1-i-1);
		while (lo < hi) {
			int mid = (lo+hi)/2+1;
			if (palin(i-mid, i+1+mid)) lo = mid;
			else hi = mid-1;
		}
		int r = lo;
		sweep[i-r].ff += 1;
		sweep[i+1].ff -= 1;
		if (r > 0) {
			sweep[i+2].ff -= 1;
			if (i+r+2 < n) sweep[i+r+2].ff += 1;
		}
		if (i+r+2 < n) sweep[i+r+2].ss -= 1;
		suma += r+1;
		if (i-r-1 < 0 || i+r+2 > n-1) continue;
		int sada = isti(i-r-2, i+r+3);
		p[s[i+r+2] - 'a'][i-r-1] += sada+1;
		p[s[i-r-1] - 'a'][i+r+2] += sada+1;
	}
	/////////////////////////////////////////////////////////////
	ll dodaj = 0;
	for (int i=0;i<n;i++) {
		dodaj += sweep[i].ff;
		mns[i] += dodaj;
		if (i > 0) mns[i] += mns[i-1];
		mns[i] += sweep[i].ss;
	//	cout << mns[i] << " ";
	}
	ll poc = suma;
	for (int i=0;i<n;i++) {
		for (int j=0;j<26;j++) {
			if (j == s[i]-'a') continue;
			suma = max(suma, poc + p[j][i] - mns[i]);
		}
	}
	cout << suma;
	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 6 ms 1664 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6904 KB Output is correct
2 Correct 46 ms 6264 KB Output is correct
3 Correct 47 ms 6264 KB Output is correct
4 Correct 48 ms 7800 KB Output is correct
5 Correct 47 ms 7672 KB Output is correct
6 Correct 49 ms 7800 KB Output is correct
7 Correct 46 ms 7708 KB Output is correct
8 Correct 40 ms 5376 KB Output is correct
9 Correct 48 ms 7712 KB Output is correct
10 Correct 54 ms 7744 KB Output is correct
11 Correct 50 ms 6136 KB Output is correct
12 Correct 56 ms 7672 KB Output is correct
13 Correct 56 ms 7672 KB Output is correct
14 Correct 47 ms 8568 KB Output is correct
15 Correct 55 ms 8568 KB Output is correct
16 Correct 63 ms 6940 KB Output is correct
17 Correct 44 ms 24888 KB Output is correct
18 Correct 50 ms 6904 KB Output is correct
19 Correct 43 ms 25720 KB Output is correct