/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <queue>
#include <unordered_map>
template <class T, class U>
bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
class range {
public:
class iterator {
private:
int64_t M_position;
public:
iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { ++M_position; }
bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
reverse_iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { --M_position; }
bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
iterator begin() const noexcept { return M_first; }
iterator end() const noexcept { return M_last; }
reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#include <type_traits>
#include <iterator>
template <class T>
class rev_impl {
public:
using iterator = decltype(std::declval<T>().rbegin());
private:
const iterator M_begin;
const iterator M_end;
public:
rev_impl(T &&cont) noexcept: M_begin(cont.rbegin()), M_end(cont.rend()) { }
iterator begin() const noexcept { return M_begin; }
iterator end() const noexcept { return M_end; }
};
template <class T>
rev_impl<T> rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
#include <cstddef>
#include <cstdint>
template <class InputIterator>
class manacher_impl {
public:
using value_type = typename InputIterator::value_type;
public:
std::vector<size_t> odd, even;
explicit manacher_impl(InputIterator first, InputIterator last, const value_type &never) {
const size_t size = std::distance(first, last);
odd.resize(size);
even.resize(size - 1);
std::vector<value_type> str;
str.reserve(2 * size + 1);
for (; first != last; ++first) {
str.push_back(never);
str.push_back(*first);
}
str.push_back(never);
std::vector<int32_t> calc(str.size());
int32_t i = 0, j = 0;
while (i < (int32_t) str.size()) {
while (i - j >= 0 && i + j < (int32_t) str.size() && str[i - j] == str[i + j]) {
++j;
}
calc[i] = j;
int32_t k = 1;
while (i - k >= 0 && k + calc[i - k] < j) {
calc[i + k] = calc[i - k];
++k;
}
i += k;
j -= k;
}
for (size_t k = 1; k + 1 < str.size(); ++k) {
if (k % 2 == 1) {
odd[k / 2] = calc[k] - 1;
}
else {
even[k / 2 - 1] = calc[k] - 1;
}
}
}
};
template <class InputIterator>
manacher_impl<InputIterator> manacher(InputIterator first, InputIterator last, const typename InputIterator::value_type &never) {
return manacher_impl<InputIterator>(first, last, never);
}
/**
* @title Manacher
*/
#include <random>
#include <chrono>
#include <type_traits>
uint64_t engine() {
static const auto rotate = [](const uint64_t x, const size_t k) {
return (x << k) | (x >> (64 - k));
};
static auto array = [] {
uint64_t seed = static_cast<uint64_t>(std::chrono::system_clock::now().time_since_epoch().count());
std::array<uint64_t, 4> res{};
for (size_t index = 0; index < 4; index++) {
uint64_t value = (seed += 0x9e3779b97f4a7c15);
value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9;
value = (value ^ (value >> 27)) * 0x94d049bb133111eb;
res[index] = value ^ (value >> 31);
}
return res;
}();
const uint64_t result = rotate(array[1] * 5, 7) * 9;
const uint64_t old_value = array[1] << 17;
array[2] ^= array[0];
array[3] ^= array[1];
array[1] ^= array[2];
array[0] ^= array[3];
array[2] ^= old_value;
array[3] = rotate(array[3], 45);
return result;
}
template <class Integer>
typename std::enable_if<std::is_integral<Integer>::value, Integer>::type random_number(Integer lower, Integer upper) {
static std::default_random_engine gen(engine());
return std::uniform_int_distribution<Integer>(lower, upper)(gen);
}
template <class Real>
typename std::enable_if<!std::is_integral<Real>::value, Real>::type random_number(Real lower, Real upper) {
static std::default_random_engine gen(engine());
return std::uniform_real_distribution<Real>(lower, upper)(gen);
}
/**
* @title Random Number
*/
#include <string>
namespace rolling_hash_detail {
class hash61_t {
public:
static uint64_t mod() {
return (static_cast<uint64_t>(1) << 61) - 1;
}
static uint32_t base() {
static const uint32_t value = static_cast<uint32_t>(engine());
return value;
}
static uint64_t add(uint64_t a, uint64_t b) {
a += b;
if (a >= mod()) a -= mod();
return a;
}
static uint64_t sub(uint64_t a, uint64_t b) {
a += mod() - b;
if (a >= mod()) a -= mod();
return a;
}
static uint64_t mul(uint64_t a, uint64_t b) {
uint64_t l1 = (uint32_t) a, h1 = a >> 32, l2 = (uint32_t) b, h2 = b >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t res = (l & mod()) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
res = (res & mod()) + (res >> 61);
res = (res & mod()) + (res >> 61);
return res - 1;
}
static std::vector<uint64_t> reserve;
static uint64_t power(const size_t index) {
if (index >= reserve.size()) {
size_t cur = reserve.size();
reserve.resize(index + 1);
for (; cur <= index; ++cur) {
reserve[cur] = mul(reserve[cur - 1], base());
}
}
return reserve[index];
}
};
std::vector<uint64_t> hash61_t::reserve = std::vector<uint64_t>(1, 1);
};
class rolling_hash {
public:
using hash_type = uint64_t;
using size_type = size_t;
private:
using op_t = rolling_hash_detail::hash61_t;
std::string M_string;
std::vector<hash_type> M_hash;
public:
rolling_hash() { initialize(); }
rolling_hash(const std::string &initial_) { construct(initial_); }
void initialize() {
clear();
M_string = "";
M_hash.assign(1, 0);
}
void construct(const std::string &initial_) {
initialize();
add_string(initial_);
}
void add_string(const std::string &str) {
size_type cur_size = M_string.size();
size_type next_size = M_string.size() + str.size();
M_string += str;
M_hash.resize(next_size + 1);
for (size_type i = cur_size; i < next_size; ++i) {
M_hash[i + 1] = op_t::add(op_t::mul(M_hash[i], op_t::base()), M_string[i]);
}
}
hash_type hash(size_type l, size_type r) const {
return op_t::sub(M_hash[r], op_t::mul(op_t::power(r - l), M_hash[l]));
}
size_type lcp(size_type l, size_type r) const {
size_type ok = 0, ng = std::min(M_string.size() - l, M_string.size() - r) + 1;
while (ng - ok > 1) {
size_type md = (ok + ng) >> 1;
(hash(l, l + md) == hash(r, r + md) ? ok : ng) = md;
}
return ok;
}
const std::string &get() const {
return M_string;
}
size_type size() const {
return M_string.size();
}
bool empty() const {
return M_string.empty();
}
void clear() {
M_string.clear();
M_string.shrink_to_fit();
M_hash.clear();
M_hash.shrink_to_fit();
}
};
/**
* @title Rolling Hash
*/
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
struct state {
i32 l, r;
explicit state(i32 l_, i32 r_): l(l_), r(r_) { }
bool operator < (const state &rhs) const {
return (r - l) < (rhs.r - rhs.l);
}
};
int main() {
std::string S;
std::cin >> S;
const auto pal = manacher(S.begin(), S.end(), '$');
const auto rh = rolling_hash(S);
std::priority_queue<state> que;
std::unordered_map<typename rolling_hash::hash_type, i32> count;
const auto push = [&](const i32 l, const i32 r) {
const auto hash = rh.hash(l, r);
if (count.count(hash) == 0) {
que.emplace(l, r);
}
count[hash]++;
};
for (auto i: range(0, S.size())) {
const i32 l = i - pal.odd[i] / 2;
const i32 r = l + pal.odd[i];
push(l, r);
}
for (auto i: range(0, S.size() - 1)) {
const i32 l = i - pal.even[i] / 2 + 1;
const i32 r = l + pal.even[i];
push(l, r);
}
i64 ans = 0;
while (!que.empty()) {
const auto top = que.top();
que.pop();
const i32 l = top.l;
const i32 r = top.r;
chmax(ans, (i64) (r - l) * count[rh.hash(l, r)]);
if (l + 1 < r - 1) {
push(l + 1, r - 1);
}
}
std::cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
0 ms |
256 KB |
Output is correct |
| 9 |
Correct |
0 ms |
256 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
8612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
276 ms |
26524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
