結果
| 問題 |
No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
|
| コンテスト | |
| ユーザー |
 hos.lyric
|
| 提出日時 | 2019-05-02 06:23:04 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 174 ms / 2,000 ms |
| コード長 | 6,179 bytes |
| コンパイル時間 | 2,441 ms |
| コンパイル使用メモリ | 166,056 KB |
| 実行使用メモリ | 119,560 KB |
| 最終ジャッジ日時 | 2024-06-22 01:04:56 |
| 合計ジャッジ時間 | 4,333 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
int[] manacher(T)(T a) {
const n = cast(int)(a.length);
int[] r = new int[n * 2];
for (int i = 0, j = 0, k; i < n * 2; i += k, j = max(j - k, 0)) {
for (; 0 <= i - j && i + j + 1 < n * 2 && a[(i - j) / 2] == a[(i + j + 1) / 2]; ++j) {}
r[i] = j;
for (k = 1; 0 <= i - k && 0 <= j - k && r[i - k] != j - k; ++k) {
r[i + k] = min(r[i - k], j - k);
}
}
return r;
}
class Eertree(int shift, char offset) {
string s;
int n;
int[] us, len, fail;
int[] next;
this(in string s) {
this.s = s;
n = cast(int)(s.length);
us = new int[n + 3];
len = new int[n + 3];
fail = new int[n + 3];
next = new int[(n + 3) << shift];
us[1] = 1; len[1] = -1; fail[1] = 1;
us[2] = 2; len[2] = 0; fail[2] = 1;
foreach (i; 0 .. n) {
const c = s[i] - offset;
int u = us[i + 2];
for (; !isSuffix(i, u); u = fail[u]) {}
if (!next[u << shift | c]) {
next[u << shift | c] = i + 3;
len[i + 3] = len[u] + 2;
if (u == 1) {
fail[i + 3] = 2;
} else {
int v = fail[u];
for (; !isSuffix(i, v); v = fail[v]) {}
fail[i + 3] = next[v << shift | c];
}
}
us[i + 3] = next[u << shift | c];
}
}
bool isSuffix(int i, int u) const {
const j = i - 1 - len[u];
return (j >= 0 && s[j] == s[i]);
}
void print() const {
void dfs(int u, string prefix, int type) {
writefln("%s%s%s %s %s", prefix, ["", "|-- ", "`-- "][type],
(len[u] <= 0) ? ("(" ~ len[u].to!string ~ ")")
: s[u - 2 - len[u] .. u - 2],
u, fail[u]);
const vs = next[u << shift .. (u + 1) << shift].filter!(v => v).array;
foreach (v; vs) {
dfs(v, prefix ~ ["", "| ", " "][type], (v == vs[$ - 1]) ? 2 : 1);
}
}
dfs(1, "", 0);
dfs(2, " ", 0);
}
}
enum LIM_LOG_N = 19;
int N;
string S;
void main() {
try {
for (; ; ) {
S = readToken();
N = cast(int)(S.length);
const rads = manacher(S);
const tree = new Eertree!(5, 'a')(S);
debug {
writeln("S = ", S);
writeln("rads = ", rads);
tree.print;
}
// [a, b)
bool isPal(int a, int b) {
assert(0 <= a && a < b && b <= N);
return (b - a <= rads[a + b - 1]);
}
int[] palsL;
foreach (i; 1 .. N + 1) {
if (isPal(0, i)) {
palsL ~= i;
}
}
auto cntR = new int[N + 1];
foreach_reverse (i; 0 .. N) {
cntR[i] = (isPal(i, N) ? 1 : 0) + cntR[i + 1];
}
debug {
writeln("palsL = ", palsL);
writeln("cntR = ", cntR);
}
auto depth = new int[N + 3];
foreach (u; 3 .. N + 3) {
if (tree.us[u] == u) {
depth[u] = depth[tree.fail[u]] + 1;
}
}
auto f = new int[][](LIM_LOG_N, N + 3);
foreach (u; 1 .. N + 3) {
f[0][u] = tree.fail[u];
}
foreach (e; 1 .. LIM_LOG_N) {
foreach (u; 1 .. N + 3) {
f[e][u] = f[e - 1][f[e - 1][u]];
}
}
long ans;
foreach (i; 1 .. N) {
const r = palsL.lowerBound(i);
int u = tree.us[i + 2];
if (tree.len[u] == i) {
u = tree.fail[u];
}
// right greedy
if (u > 2 && isPal(0, i - tree.len[u])) {
const l = palsL.upperBound(i - tree.len[u]);
int lo = l - 1, hi = r;
for (; lo + 1 < hi; ) {
const mid = (lo + hi) / 2;
isPal(palsL[mid], i) ? (hi = mid) : (lo = mid);
}
debug {
writeln("right ", S[0 .. i - tree.len[u]], "|", S[i - tree.len[u] .. i]);
writeln(" [", l, ", ", r, ") ", hi);
int cnt;
foreach (j; 1 .. i) {
if (isPal(0, j) && isPal(j, i)) {
++cnt;
}
}
assert(cnt == 1 + (r - hi));
}
ans += 1L * (1 + (r - hi)) * cntR[i + 1];
continue;
}
// left greedy
if (r > 0 && isPal(palsL[r - 1], i)) {
int sum = 0;
if (tree.len[u] > i - palsL[r - 1] && isPal(0, i - tree.len[u])) {
int v = u;
foreach_reverse (e; 0 .. LIM_LOG_N) {
const w = f[e][v];
if (tree.len[w] > i - palsL[r - 1] && isPal(0, i - tree.len[w])) {
sum |= 1 << e;
v = w;
}
}
++sum;
}
debug {
writeln("left ", S[0 .. palsL[r - 1]], "|", S[palsL[r - 1] .. i]);
writeln(" ", sum);
int cnt;
foreach (j; 1 .. i) {
if (isPal(0, j) && isPal(j, i)) {
++cnt;
}
}
assert(cnt == 1 + sum);
}
ans += 1L * (1 + sum) * cntR[i + 1];
continue;
}
}
writeln(ans);
}
} catch (EOFException e) {
}
}