oj.uz

Submission #204748

# Submission time Handle Problem Language Result Execution time Memory
204748 2020-02-26T20:10:53 Z staniewzki Palindromes (APIO14_palindrome) C++17
100 / 100
 606 ms 31428 KB 
#include<bits/stdc++.h>
using namespace std;
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.first << ", " << p.second << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
template<class T> int size(T && a) { return a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

struct SuffixArray {
	vector<int> sa, lcp, rank;
	SuffixArray(string& s, int lim = 256) { // lub basic_string<int>
		int n = size(s) + 1, k = 0, a, b;
		vector<int> x(s.begin(), s.end() + 1);
		vector<int> y(n), ws(max(n, lim));
		sa = lcp = rank = y;
		iota(sa.begin(), sa.end(), 0);

		for(int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j;
			iota(y.begin(), y.end(), n - j);
			REP(i, n) if(sa[i] >= j)
				y[p++] = sa[i] - j;
			fill(ws.begin(), ws.end(), 0);
			REP(i, n) ws[x[i]]++;
			FOR(i, 1, lim - 1) ws[i] += ws[i - 1];
			for(int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y);
			p = 1, x[sa[0]] = 0;
			FOR(i, 1, n - 1) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		FOR(i, 1, n - 1) rank[sa[i]] = i;
		for(int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for(k && k--, j = sa[rank[i] - 1];
				s[i + k] == s[j + k]; k++);
	}
	int operator[](int x) { return sa[x]; }
};

struct RMQ {
	vector<vector<int>> st;
	vector<int> pre;
	RMQ(vector<int> a) {
		int n = size(a), lg = 0;
		while((1 << lg) < n) lg++;
		st.resize(lg + 1, vector<int>(a));
		st[0] = a;
		FOR(i, 1, lg) REP(j, n) {
			st[i][j] = st[i - 1][j];
			int q = j + (1 << (i - 1));
			if(q < n) st[i][j] = min(st[i][j], st[i - 1][q]);
		}
		pre.resize(n + 1);
		FOR(i, 2, n) pre[i] = pre[i / 2] + 1;
	}

	int query(int l, int r) {
		int q = pre[r - l + 1], x = r - (1 << q) + 1;
		return min(st[q][l], st[q][x]);
	}
};

array<vector<int>, 2> manacher(string &in) {
	int n = size(in);
	array<vector<int>, 2> radius = {{vector<int>(n - 1), vector<int>(n)}};
	REP(parity, 2) {
		int z = parity ^ 1, L = 0, R = 0;
		REP(i, n - z) {
			int &rad = radius[parity][i];
			if(i <= R - z)
				rad = min(R - i, radius[parity][L + (R - i - z)]);
			int l = i - rad + z, r = i + rad;
			while(0 <= l - 1 && r + 1 < n && in[l - 1] == in[r + 1])
				++rad, ++r, --l;
			if(r > R)
				L = l, R = r;
		}
	}
	return radius;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string str;
	cin >> str;

	int n = size(str);
	SuffixArray sa(str);
	RMQ rmq(sa.lcp);

	auto get_lcp = [&](int i, int j) {
		if(i == j) return n - i;
		i = sa.rank[i], j = sa.rank[j];
		if(i > j) swap(i, j);
		return rmq.query(i + 1, j);
	};

	auto compare = [&](int a, int b, int i, bool equal) {
		int l = get_lcp(a, i);
		if(l >= b - a + 1) return equal;
		if(i + l == n) return false;
		return str[a + l] < str[i + l];
	};

	auto binsearch = [&](int a, int b, bool equal) {
		int l = 1, r = n + 1;
		while(l < r) {
			int mid = (l + r) / 2;
			if(compare(a, b, sa[mid], equal))
				r = mid;
			else
				l = mid + 1;
		}
		return l;
	};

	auto count = [&](int a, int b) -> LL {
		return binsearch(a, b, false) - binsearch(a, b, true);
	};

	auto m = manacher(str);
	LL ans = 0;
	REP(p, 2) REP(i, n + p - 1) {
		int l = i - m[p][i] + 1 - p;
		int r = i + m[p][i];
		if(l <= r) ans = max(ans, count(l, r) * (r - l + 1));
	}

	cout << ans << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 296 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 380 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 248 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 444 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1144 KB Output is correct
2 Correct 10 ms 1144 KB Output is correct
3 Correct 12 ms 1144 KB Output is correct
4 Correct 12 ms 1144 KB Output is correct
5 Correct 11 ms 1144 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 11 ms 1144 KB Output is correct
8 Correct 10 ms 1144 KB Output is correct
9 Correct 10 ms 1144 KB Output is correct
10 Correct 11 ms 1144 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10000 KB Output is correct
2 Correct 71 ms 9992 KB Output is correct
3 Correct 95 ms 9948 KB Output is correct
4 Correct 108 ms 9952 KB Output is correct
5 Correct 107 ms 9952 KB Output is correct
6 Correct 94 ms 9952 KB Output is correct
7 Correct 91 ms 9952 KB Output is correct
8 Correct 101 ms 10080 KB Output is correct
9 Correct 129 ms 9924 KB Output is correct
10 Correct 119 ms 9948 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 31296 KB Output is correct
2 Correct 229 ms 31172 KB Output is correct
3 Correct 324 ms 31168 KB Output is correct
4 Correct 327 ms 31428 KB Output is correct
5 Correct 425 ms 31172 KB Output is correct
6 Correct 311 ms 31296 KB Output is correct
7 Correct 311 ms 31168 KB Output is correct
8 Correct 428 ms 31296 KB Output is correct
9 Correct 411 ms 31172 KB Output is correct
10 Correct 510 ms 31296 KB Output is correct
11 Correct 259 ms 31160 KB Output is correct
12 Correct 606 ms 31424 KB Output is correct