QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #646667 | #275. Palindromes | makrav | 0 | 1ms | 3844kb | C++20 | 9.0kb | 2024-10-17 02:54:44 | 2024-10-17 02:54:44 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
vector<int> manacher(string s) {
vector<int> ans(s.size());
int l = -1, r = -1;
for (int i = 0; i < s.size(); i++) {
if (i > r) {
l = i; r = i;
while (l - 1 >= 0 && r + 1 < s.size() && s[l - 1] == s[r + 1]) { r++; l--; }
ans[i] = r - l + 1;
} else {
int cl = ans[l + r - i];
if (cl / 2 + i < r) {
ans[i] = cl;
} else {
ans[i] = 1 + (r - i) * 2;
while (r + 1 < s.size() && 2 * i - (r + 1) >= 0 && s[r + 1] == s[2 * i - (r + 1)]) {
ans[i] += 2;
r++;
l = 2 * i - r;
}
}
}
}
return ans;
}
const ll mod1 = 1e9 + 7, mod2 = 998244353;
const ll p = 31;
struct polyhash {
int n;
vector<int> c;
vector<pair<ll, ll>> h, ppow;
polyhash() = default;
polyhash(int n_, vector<int> c_) {
n = n_;
c = c_;
h.assign(n + 1, {0, 0});
ppow.assign(n + 1, {1, 1});
for (int i = 1; i <= n; i++) {
h[i] = {(h[i - 1].first * p + c[i - 1]) % mod1,
(h[i - 1].second * p + c[i - 1]) % mod2};
ppow[i] = {(ppow[i - 1].first * p) % mod1,
(ppow[i - 1].second * p) % mod2};
}
}
pair<ll, ll> substring(int l, int r) {
// [l, r] is segment in 0-index
return {(h[r + 1].first + mod1 - (h[l].first * ppow[r - l + 1].first) % mod1) % mod1,
(h[r + 1].second + mod2 - (h[l].second * ppow[r - l + 1].second) % mod2) % mod2};
}
int find_lcp(int p1, int p2) {
// finds longest common prefix of suffixes starts with indexes p1 and p2
// useful for suffix array
int L = 0, R = min(n - p1, n - p2) + 1;
while (R - L > 1) {
int M = (L + R) / 2;
if (substring(p1, p1 + M - 1) == substring(p2, p2 + M - 1)) L = M;
else R = M;
}
return L;
}
};
struct sufarr {
int n;
vector<int> a;
vector<int> cl;
sufarr() = default;
sufarr(int n_, vector<int> a_) {
n = n_;
a = a_;
build();
}
void build() {
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [&](int i, int j){return a[i] < a[j];});
vector<pair<int, int>> lol(n);
cl.assign(n, 0);
int cur = -1;
for (int i = 0; i < n; i++) {
if (i == 0 || a[ord[i]] != a[ord[i - 1]]) cur++;
cl[ord[i]] = cur;
}
for (int len = 2; len < 2 * n; len *= 2) {
int l2 = len / 2;
for (int i = 0; i < n; i++) {
lol[i] = {cl[i], (i + l2 < n ? cl[i + l2] : -1)};
}
iota(all(ord), 0);
vector<int> no;
{
vector<vector<int>> bs(n + 1);
for (int i = 0; i < n; i++) bs[lol[ord[i]].second + 1].pb(ord[i]);
no.clear();
for (int i = 0; i < n; i++) {
for (int el : bs[i]) no.pb(el);
}
swap(no, ord);
}
{
vector<vector<int>> bs(n);
for (int i = 0; i < n; i++) bs[lol[ord[i]].first].pb(ord[i]);
no.clear();
for (int i = 0; i < n; i++) {
for (int el : bs[i]) no.pb(el);
}
swap(no, ord);
}
//sort(all(ord), [&](int i, int j){return lol[i] < lol[j];});
int cur = -1;
for (int j = 0; j < n; j++) {
if (j == 0 || lol[ord[j]] != lol[ord[j - 1]]) cur++;
cl[ord[j]] = cur;
}
}
}
};
struct fenwick {
int n;
vector<int> t;
fenwick() = default;
fenwick(int n_) {
n = n_;
t.assign(n + 1, 0);
}
void upd(int p, int vl) {
for (; p <= n; p = (p | (p + 1))) t[p] += vl;
}
int get(int p) {
int sm = 0;
for (; p > 0; p = (p & (p + 1)) - 1) sm += t[p];
return sm;
}
int get_seg(int l, int r) {
return get(r) - get(l - 1);
}
};
void solve() {
string s; cin >> s;
int n = s.size();
vector<int> arr(s.size());
for (int i = 0; i < n; i++) arr[i] = (s[i] - 'a' + 1);
string nww = ".";
for (int i = 0; i < s.size(); i++) {
nww += s[i];
nww += '.';
}
auto result = manacher(nww);
sufarr sf(n, arr);
vector<int> order(n), pos = sf.cl;
for (int i = 0; i < n; i++) order[sf.cl[i]] = i;
// for (int x : order){
// for (int j = x; j < n; j++) cout << s[j];
// cout << '\n';
// }
polyhash pl(n, arr);
vector<int> lcp(n - 1);
for (int i = 0; i < n - 1; i++) {
lcp[i] = pl.find_lcp(order[i], order[i + 1]);
//cout << order[i] << ' ' << order[i + 1] << '\n';
}
ll ans = 0;
{
fenwick fw(n + 10);
multiset<int> segs;
vector<vector<int>> turnoff(n + 1), turnon_gr(n + 1);
for (int i = 1; i < sz(nww); i += 2) {
int ml = result[i] / 2;
//cout << i / 2 << ' ' << result[i] / 2 << " fuck\n";
turnoff[ml / 2 + 1].pb(pos[i / 2]);
}
for (int i = 0; i < n - 1; i++) {
//cout << lcp[i] << ' ';
turnon_gr[lcp[i]].pb(i);
}
//cout << " lcps\n";
for (int i = 0; i < n; i++) fw.upd(i + 1, 1);
set<int> brds;
brds.insert(-1); brds.insert(n - 1);
segs.insert(n);
for (int len = 0; len <= n; len++) {
for (int el : turnoff[len]) {
fw.upd(el + 1, -1);
auto nxt = brds.lower_bound(el);
int prv = *(--nxt);
int nxt_val = *(++nxt);
int cs = fw.get_seg(prv + 2, nxt_val + 1);
segs.erase(segs.find(cs + 1));
segs.insert(cs);
}
for (int el : turnon_gr[len]) {
auto nxt = brds.lower_bound(el);
int prv = *(--nxt);
int nxt_val = *(++nxt);
int cs = fw.get_seg(prv + 2, nxt_val + 1);
segs.erase(segs.find(cs));
int neww_s1 = fw.get_seg(prv + 2, el + 1), neww_s2 = fw.get_seg(el + 2, nxt_val + 1);
segs.insert(neww_s1);
segs.insert(neww_s2);
brds.insert(el);
}
//cout << 2 * len + 1 << ' ' << (*segs.rbegin()) << '\n';
ans = max(ans, (*segs.rbegin()) * 1ll * (2 * len + 1));
}
}
{
fenwick fw(n + 10);
multiset<int> segs;
vector<vector<int>> turnoff(n + 1), turnon_gr(n + 1);
for (int i = 2; i < sz(nww) - 1; i += 2) {
//cout << i << ' ' << result[i] / 2 << "fuckxd\n";
int ml = result[i] / 2;
turnoff[ml / 2 + 1].pb(pos[i / 2]);
}
for (int i = 0; i < n - 1; i++) {
turnon_gr[lcp[i]].pb(i);
}
for (int i = 1; i < n; i++) {
fw.upd(pos[i] + 1, 1);
}
set<int> brds;
brds.insert(-1); brds.insert(n - 1);
segs.insert(n - 1);
for (int len = 1; len <= n; len++) {
for (int el : turnoff[len]) {
//cout << el << ' ';
fw.upd(el + 1, -1);
auto nxt = brds.lower_bound(el);
int prv = *(--nxt);
int nxt_val = *(++nxt);
int cs = fw.get_seg(prv + 2, nxt_val + 1);
segs.erase(segs.find(cs + 1));
segs.insert(cs);
}
//cout << '\n';
for (int el : turnon_gr[len - 1]) {
auto nxt = brds.lower_bound(el);
int prv = *(--nxt);
int nxt_val = *(++nxt);
int cs = fw.get_seg(prv + 2, nxt_val + 1);
segs.erase(segs.find(cs));
int neww_s1 = fw.get_seg(prv + 2, el + 1), neww_s2 = fw.get_seg(el + 2, nxt_val + 1);
segs.insert(neww_s1);
segs.insert(neww_s2);
brds.insert(el);
}
ans = max(ans, (*segs.rbegin()) * 1ll * (2 * len));
//cout << 2 * len << ' ' << (*segs.rbegin()) << '\n';
}
}
cout << ans << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 8
Accepted
time: 1ms
memory: 3576kb
input:
abacaba
output:
7
result:
ok single line: '7'
Test #2:
score: 8
Accepted
time: 0ms
memory: 3640kb
input:
www
output:
4
result:
ok single line: '4'
Test #3:
score: 8
Accepted
time: 0ms
memory: 3584kb
input:
abacababa
output:
9
result:
ok single line: '9'
Test #4:
score: 8
Accepted
time: 0ms
memory: 3588kb
input:
r
output:
1
result:
ok single line: '1'
Test #5:
score: 8
Accepted
time: 0ms
memory: 3652kb
input:
xd
output:
1
result:
ok single line: '1'
Test #6:
score: 8
Accepted
time: 0ms
memory: 3576kb
input:
dd
output:
2
result:
ok single line: '2'
Test #7:
score: 8
Accepted
time: 0ms
memory: 3580kb
input:
opo
output:
3
result:
ok single line: '3'
Test #8:
score: 8
Accepted
time: 0ms
memory: 3588kb
input:
opoo
output:
3
result:
ok single line: '3'
Test #9:
score: 8
Accepted
time: 0ms
memory: 3844kb
input:
abacabadabacaba
output:
15
result:
ok single line: '15'
Test #10:
score: 8
Accepted
time: 0ms
memory: 3576kb
input:
xxxxxyxxxxyxxxxx
output:
24
result:
ok single line: '24'
Test #11:
score: 8
Accepted
time: 0ms
memory: 3580kb
input:
xxxyxxxyzzzabcdxxdcba
output:
10
result:
ok single line: '10'
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3580kb
input:
qpppppppwowpppppq
output:
35
result:
wrong answer 1st lines differ - expected: '24', found: '35'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%