QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291188 | #2996. 字符串问题 | MoRanSky | 100 ✓ | 2278ms | 396828kb | C++23 | 3.5kb | 2023-12-26 05:17:29 | 2023-12-26 05:17:30 |
Judging History
answer
// Skyqwq
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef map<int, int>::iterator MIT;
const int N = 2e5 + 5, S = N * 6, M = N * 7, L = 19;
int n, m, na, nb, La[N], Ra[N], Lb[N], Rb[N], fa[S][L], dep[S], q[S], in[S];
LL f[S], w[S];
char s[N];
map<int, int> mp[S];
int head[S], numE = 0, cnt;
struct E{
int next, v;
} e[M];
int last = 1, idx = 1, pos[N];
vector<int> g[S];
struct SAM{
int ch[26], link, len;
} t[S];
void inline insert(int c, int i) {
int x = ++idx, p = last; t[x].len = t[p].len + 1; pos[i] = x;
while (p && !t[p].ch[c]) t[p].ch[c] = x, p = t[p].link;
if (!p) t[x].link = 1;
else {
int q = t[p].ch[c];
if (t[p].len + 1 == t[q].len) t[x].link = q;
else {
int y = ++idx; t[y] = t[q], t[y].len = t[p].len + 1;
while (p && t[p].ch[c] == q) t[p].ch[c] = y, p = t[p].link;
t[q].link = t[x].link = y;
}
}
last = x;
}
void inline add(int u, int v) {
in[v]++;
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
void inline clear() {
for (int i = 1; i <= n; i++) pos[i] = 0;
for (int i = 0; i <= na + nb + cnt; i++) {
dep[i] = 0, head[i] = 0;
g[i].clear(), mp[i].clear(), in[i] = 0;
for (int j = 0; j < 26; j++) t[i].ch[j] = 0;
t[i].len = t[i].link = 0;
for (int j = 0; j < L; j++) fa[i][j] = 0;
}
numE = 0; last = 1, idx = 1;
}
void dfs(int u) {
for (int i = 1; i < L; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa[u][0]) continue;
dep[v] = dep[u] + 1, fa[v][0] = u;
dfs(v);
}
}
int inline get(int l, int r) {
int x = pos[r], len = r - l + 1;
for (int i = L - 1; ~i; i--)
if (len <= t[fa[x][i]].len) x = fa[x][i];
if (!mp[x].count(len)) mp[x][len] = ++cnt;
return mp[x][len];
}
void inline change(int &x, int &y) {
int t1 = n - y + 1, t2 = n - x + 1;
x = t1, y = t2;
}
LL inline toposort() {
int hh = 1, tt = 0; LL res = 0;
for (int i = 1; i <= na + nb + cnt; i++) {
if (!in[i]) q[++tt] = i;
f[i] = w[i] = i <= na ? Ra[i] - La[i] + 1 : 0;
}
while (hh <= tt) {
int u = q[hh++]; res = max(res, f[u]);
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
f[v] = max(f[v], f[u] + w[v]);
if (--in[v] == 0) q[++tt] = v;
}
}
if (tt != na + nb + cnt) return -1;
return res;
}
int main() {
int T; scanf("%d", &T);
for (int ca = 1; ca <= T; ca++) {
scanf("%s%d", s + 1, &na); n = strlen(s + 1);
reverse(s + 1, s + 1 + n);
for (int i = 1; i <= n; i++) insert(s[i] - 'a', i);
for (int i = 1; i <= idx; i++) mp[i][t[i].len] = i;
cnt = idx;
for (int i = 2; i <= idx; i++) g[t[i].link].push_back(i);
dfs(1);
for (int i = 1; i <= na; i++) scanf("%d%d", La + i, Ra + i), change(La[i], Ra[i]);
scanf("%d", &nb);
for (int i = 1; i <= nb; i++) scanf("%d%d", Lb + i, Rb + i), change(Lb[i], Rb[i]);
for (int i = 1; i <= na; i++) add(get(La[i], Ra[i]) + na + nb, i);
for (int i = 1; i <= nb; i++) add(i + na, get(Lb[i], Rb[i]) + na + nb);
for (int i = 1; i <= idx; i++) {
int t = -1;
if (mp[fa[i][0]].size()) t = (--mp[fa[i][0]].end()) -> second;
for (MIT it = mp[i].begin(); it != mp[i].end(); it++) {
if (t != -1) add(t + na + nb, it -> second + na + nb);
t = it -> second;
}
}
scanf("%d", &m);
while (m--) {
int x, y; scanf("%d%d", &x, &y);
add(x, na + y);
}
printf("%lld\n", toposort());
clear();
}
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 30ms
memory: 110032kb
input:
39 feyqwovxbehhhyykvnpmukgbaxtvurzvefkdodefqcefjeargabaccbawcaccbcbbbaacbfabbabaqacabaabbbbacczabcbabcbacacccapacabbccabaabaaacaaacabbcacbbbbbccbcabcccbbabbbacabbccaabababcabaaabbcbcbcabaccacaabaaaaaaaacbcacccbcbbbbaababcaccbbcabbcccbcccacabbcabacbcbbbaacabbabababcbcabcacbaccbcaaaaabbaacacbccacbacab...
output:
-1 -1 -1 190 -1 164 166 124 143 -1 -1 -1 77 -1 130 128 -1 93 -1 141 155 166 90 -1 126 140 157 147 172 211 173 125 -1 135 -1 -1 150 -1 94
result:
ok 39 lines
Test #2:
score: 10
Accepted
time: 475ms
memory: 186008kb
input:
30 glhfabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaabglhfabbaabbabaababbabaabbaababbaa...
output:
520 11636 8316 -1 396669 -1 350903 -1 15905 72960 36798 17488 42761 39434 26279 32797 -1 32042 -1 27408 19823 24985 32314 -1 37908 31169 22963 39115 28035 47216
result:
ok 30 lines
Test #3:
score: 10
Accepted
time: 462ms
memory: 186072kb
input:
29 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
-1 7400 11278 -1 -1 208692 474219 227871 33959 46213 44661 16603 32041 38509 31999 36344 16953 14347 44406 38540 16170 14572 15839 29668 25281 50172 -1 -1 -1
result:
ok 29 lines
Test #4:
score: 10
Accepted
time: 929ms
memory: 235480kb
input:
10 hwjtltzilyfsusnhgiiocavujiaordjtgmtvfacaoiwrypgvtpcjddonbncqqwbxnoajiysnijzabynekoyknnlhvnfjtzcjmfmaknqprfuvtajlbgyqiybpohfvvtarjmuersynvppjrrdapgclodkbvzueeasqsyqhtbwmqauxjcqnsacpvnhsexsswvefricteedsenmlixgvozclwsvjeijvmwmlybjrlafknhdbgpirovdddrwkyiiwwarkpcbezbrjutwwporlbngviuhurixhqdlageggeauvz...
output:
-1 -1 -1 199914 199929 199873 -1 199905 -1 199957
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 1200ms
memory: 276336kb
input:
51 wwwgrmskhauxztuyflowbcqctyplrcbyqyqptvnsptwnyptlymjrlglmhevhpiazuryqespxskopjkadwcbxeidlvipouzfdpnbwafvkgxvlsqsekspqftipymojxlwgprreagzbeasigcjbudvnzsnvohnuplllsnyucexakvbxbmxodrcpdhhyawbolwxlyifppayhzzeckibvvlpogxqmucyuzcahvnvoskwinuuqkkwmqqqxfkorzsiwrripxkjvstxbxhmkwwwqyjqjqicphgajewwxqwrvticen...
output:
94331 104718 96829 106368 -1 7495 3097 -1 -1 -1 -1 369 -1 384 -1 -1 -1 -1 128 -1 353 -1 335 -1 -1 111 -1 176 -1 -1 242 -1 -1 -1 -1 311 -1 -1 302 -1 -1 -1 -1 -1 -1 315 171 -1 308 -1 -1
result:
ok 51 lines
Test #6:
score: 10
Accepted
time: 1258ms
memory: 281164kb
input:
44 ixhuitywihrcjeipcicrhkxxolouyjwnlcbgjqleiyxlrjsgupohhyvlmtaqesonoyrhsyulmtbegrqvtvsfxjnjlgjekqyaqzpfmwyouavubxmcxrzhjabaodkawfkajdsraxcptqsyleeymvfxqkdrjktonfezutfkkzfxcrtqolaahthrbulyjaffspdotvgdbjvennbintmrqnkjqndrilksjrakgkhcglfmanjplbhedebdmkgxolwrpydcsstptezgxrjgyirrtwxywwoyrghrztlpzkeprwhvm...
output:
110089 98880 100758 104230 -1 4378 4495 4898 -1 -1 -1 -1 282 263 196 -1 -1 -1 -1 421 283 303 224 -1 -1 -1 223 331 -1 -1 -1 181 336 -1 -1 -1 469 -1 252 -1 -1 -1 -1 355
result:
ok 44 lines
Test #7:
score: 10
Accepted
time: 1741ms
memory: 318476kb
input:
100 glhfabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabba...
output:
131080 213027672 200450529 201721754 203425350 59784340 62075296 59178758 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 55 -1 -1 107 15 -1 -1 -1 54 -1 -1 -1 -1 -1 -1 15 61 107 86 131 30 -1 -1 -1 -1 39 85 44 26 -1 -1 -1 26 -1 -1 35 110 28 -1 -1 -1 -1 16 -1 -1 -1 68 91 59 -1 -1 -1 -1 111 86 -1 -1 -1 85 -1...
result:
ok 100 lines
Test #8:
score: 10
Accepted
time: 1681ms
memory: 316752kb
input:
100 hggafwsdmxivpnfcjwubzgvaomzilopymnekzlqijbtgujdxpwowbkciohxtkjgmrodlbqsjfnxnynzexbndxukjegrfyiuvktvzxaidfvvgxqwhxxwroprmrtxmbhrulqzerqehjmxzthuirnwhuswqnhysgbjwrbadqraltvkkbbnkfdjyvwuvszcgooizqtjwkbzzosnoututkmeqbynrbbhbjliveufgbfjnwsucnopjdkcfxpcjoptbwgmordieneuaduynfxddisexmcnbinmeyeolobrmfdqz...
output:
-1 208905485 205523915 202863858 206244046 60152261 59695786 63478009 -1 -1 -1 -1 -1 -1 97 -1 -1 -1 25 10 -1 -1 -1 -1 -1 16 -1 112 -1 185 46 26 -1 -1 61 -1 -1 -1 -1 -1 142 -1 -1 -1 35 93 -1 55 -1 -1 71 46 -1 35 -1 -1 -1 10 36 -1 -1 -1 -1 -1 68 74 -1 -1 -1 -1 5 -1 -1 56 -1 -1 -1 -1 -1 -1 14 -1 -1 -1 ...
result:
ok 100 lines
Test #9:
score: 10
Accepted
time: 2189ms
memory: 395948kb
input:
100 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
20000100000 62516258 58379078 203874157 200936649 650929 -1 1666983 96590 106367 136970 83485 -1 106132 98111 60799 93680 55617 1076 457 413 602 303 436 419 104 325 -1 494 202 -1 288 -1 429 600 324 286 370 390 477 272 627 495 1319 671 509 208 280 184 71 537 407 380 452 327 -1 773 205 247 -1 430 441 ...
result:
ok 100 lines
Test #10:
score: 10
Accepted
time: 2278ms
memory: 396828kb
input:
100 boicmuspttnwpilgnszaafnuxghguuqaxdoeoispntpabpmhtozzqzzzmzzzzzzzzzzzrzzzzzzzzzzzzzzzzzzxzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzznzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
19570070095 56191677 57572613 201905229 201099444 689056 -1 -1 140456 94558 53299 112449 62781 74284 -1 -1 57230 -1 148 548 -1 666 651 -1 305 412 616 592 291 235 463 253 461 -1 621 168 -1 808 -1 560 134 354 215 88 226 548 169 570 663 302 -1 115 234 299 171 525 600 549 170 347 414 300 461 313 -1 442 ...
result:
ok 100 lines
Extra Test:
score: 0
Extra Test Passed