QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86180 | #5256. Insertions | 5ab | TL | 20ms | 12960kb | C++17 | 4.2kb | 2023-03-09 14:53:37 | 2023-03-09 14:53:40 |
Judging History
answer
/* name: 5256
* author: 5ab
* created at: 2023-03-08
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int max_n = 100000;
int ld[max_n + 1], rd[max_n + 1], cans[max_n + 1], fl[max_n * 2 + 1];
struct Tr
{
int hd[max_n + 1], st[max_n + 1], ed[max_n + 1], fa[max_n + 1], ind = 0;
int des[max_n], nxt[max_n], e_cnt = 0;
Tr() { memset(hd, -1, sizeof hd); }
void add(int s, int t)
{
des[e_cnt] = t;
nxt[e_cnt] = hd[s];
hd[s] = e_cnt++;
}
void dfs(int id)
{
st[id] = ind++;
for (int p = hd[id], dst; p != -1; p = nxt[p])
{
dst = des[p];
dfs(dst);
}
ed[id] = ind;
}
} T1, T2;
struct fwt
{
int tr[max_n + 2], n;
static inline int lowbit(int x) { return x & -x; }
void clear() { memset(tr, 0, sizeof tr); }
void add(int x, int v)
{
for (x++; x <= n; x += lowbit(x))
tr[x] += v;
}
int get(int x)
{
int res = 0;
for (x++; x; x -= lowbit(x))
res += tr[x];
return res;
}
} f;
char ts[max_n * 2 + 1];
vector<int> qr[max_n + 1];
int sl, tl, pl;
void getfail(int *fail, int n)
{
fail[0] = 0;
// cerr << ts << endl;
for (int i = 1, j = 0; i < n; i++)
{
while (j && ts[i] != ts[j]) j = fail[j - 1];
fail[i] = (j += (ts[i] == ts[j]));
}
// for (int i = 0; i < n; i++)
// cerr << fail[i] << " \n"[i == n - 1];
}
void buildtree(int n, Tr& tr)
{
tr.fa[0] = -1;
for (int i = 0; i < n; i++)
{
tr.add(fl[i], i + 1);
tr.fa[i + 1] = fl[i];
}
tr.dfs(0);
}
void solve1(Tr& t1, Tr& t2, int *d)
{
getfail(fl, tl + pl + 1);
int tx = fl[tl + pl];
for (int x = tx == min(pl, tl) ? t2.fa[tx] : tx; x != 0; x = t2.fa[x])
{
f.add(t1.st[pl - x], 1);
f.add(t1.ed[pl - x], -1);
// cerr << x << " " << t1.st[pl - x] << endl;
}
for (int i = 0; i <= sl; i++)
{
cans[i] += f.get(t1.st[d[i]]);
// cerr << d[i] << "," << t1.st[d[i]] << " \n"[i == sl];
}
f.clear();
for (int i = 0; i <= sl; i++)
cerr << cans[i] << " \n"[i == sl];
}
void solve2(int x)
{
if (x + tl <= pl && fl[tl + tl + x] == tl)
{
f.add(T2.st[pl - tl - x], 1);
f.add(T2.ed[pl - tl - x], -1);
}
for (int qry : qr[x])
cans[qry] += f.get(T2.st[rd[qry]]);
for (int p = T1.hd[x]; p != -1; p = T1.nxt[p])
solve2(T1.des[p]);
if (x + tl <= pl && fl[tl + tl + x] == tl)
{
f.add(T2.st[pl - tl - x], -1);
f.add(T2.ed[pl - tl - x], 1);
}
}
char s[max_n + 1], t[max_n + 1], p[max_n + 1];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> t >> p;
sl = strlen(s), tl = strlen(t), pl = strlen(p), f.n = pl + 1;
copy(s, s + sl, copy(p, p + pl, ts) + 1), ts[pl] = '$';
getfail(fl, sl + pl + 1);
buildtree(pl, T1);
copy(fl + pl, fl + sl + pl + 1, ld);
int bsn = 0;
for (int i = pl; i <= sl; i++)
bsn += (ld[i] == pl);
for (int i = 0; i <= sl; i++)
{
bsn += (ld[i] == pl);
cans[i] += bsn;
if (i + pl <= sl)
bsn -= (ld[i + pl] == pl);
}
copy(p, p + pl, copy(s, s + sl, ts) + 1), ts[sl] = '$';
reverse(ts, ts + pl + sl + 1);
getfail(fl, sl + pl + 1);
buildtree(pl, T2);
copy(fl + pl, fl + sl + pl + 1, rd);
reverse(rd, rd + sl + 1);
copy(p, p + pl, copy(t, t + tl, ts) + 1), ts[tl] = '$';
solve1(T1, T2, ld);
copy(t, t + tl, copy(p, p + pl, ts) + 1), ts[pl] = '$';
solve1(T2, T1, rd);
if (pl <= tl)
{
int ans = -1, lmx = -1, rmx = -1, cnt = 0;
for (int i = 0; i <= sl; i++)
if (cans[i] > ans)
lmx = rmx = i, ans = cans[i], cnt = 1;
else if (ans == cans[i])
rmx = i, cnt++;
for (int i = 0; i < tl; i++)
ans += (fl[pl + i + 1] == pl);
cout << ans << " " << cnt << " " << lmx << " " << rmx << endl;
return 0;
}
copy(p, p + pl, copy(t, t + tl, ts) + 1), ts[tl] = '$';
getfail(fl, tl + pl + 1);
for (int i = 0; i <= sl; i++)
qr[ld[i]].push_back(i);
solve2(0);
int ans = -1, lmx = -1, rmx = -1, cnt = 0;
for (int i = 0; i <= sl; i++)
if (cans[i] > ans)
lmx = rmx = i, ans = cans[i], cnt = 1;
else if (ans == cans[i])
rmx = i, cnt++;
cout << ans << " " << cnt << " " << lmx << " " << rmx << endl;
return 0;
}
// started coding at: 03-08 18:01:14
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 11508kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 12092kb
input:
z zzkkzzkk z
output:
5 2 0 1
result:
ok 4 number(s): "5 2 0 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11540kb
input:
wgwwggggw g gggg
output:
2 5 4 8
result:
ok 4 number(s): "2 5 4 8"
Test #4:
score: 0
Accepted
time: 1ms
memory: 12636kb
input:
q uuquu u
output:
4 2 0 1
result:
ok 4 number(s): "4 2 0 1"
Test #5:
score: 0
Accepted
time: 5ms
memory: 11672kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 4ms
memory: 12048kb
input:
p xpxp p
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #7:
score: 0
Accepted
time: 6ms
memory: 11548kb
input:
aacaacacaa ca caca
output:
2 5 2 9
result:
ok 4 number(s): "2 5 2 9"
Test #8:
score: 0
Accepted
time: 2ms
memory: 11532kb
input:
k kekekkekk k
output:
7 2 0 1
result:
ok 4 number(s): "7 2 0 1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 11452kb
input:
ghhhhg g ghhg
output:
2 1 3 3
result:
ok 4 number(s): "2 1 3 3"
Test #10:
score: 0
Accepted
time: 5ms
memory: 11236kb
input:
b xbb b
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #11:
score: 0
Accepted
time: 3ms
memory: 11008kb
input:
nddnnndndn dnd ndndn
output:
3 1 5 5
result:
ok 4 number(s): "3 1 5 5"
Test #12:
score: 0
Accepted
time: 2ms
memory: 11304kb
input:
imiimmmm miimi i
output:
6 9 0 8
result:
ok 4 number(s): "6 9 0 8"
Test #13:
score: 0
Accepted
time: 5ms
memory: 11508kb
input:
gzzzzzzzzz zgzzzg gzgggzzz
output:
0 11 0 10
result:
ok 4 number(s): "0 11 0 10"
Test #14:
score: 0
Accepted
time: 6ms
memory: 11876kb
input:
m mmwmwmw wwmww
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #15:
score: 0
Accepted
time: 1ms
memory: 11800kb
input:
jmmmmjmmj jmjjjmjm mjmmmmjj
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #16:
score: 0
Accepted
time: 2ms
memory: 11984kb
input:
f ffffwff wffw
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #17:
score: 0
Accepted
time: 4ms
memory: 11640kb
input:
plpll llplll pppppppl
output:
0 6 0 5
result:
ok 4 number(s): "0 6 0 5"
Test #18:
score: 0
Accepted
time: 2ms
memory: 12352kb
input:
yypppypyy ppyyypppy ypyppypp
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #19:
score: 0
Accepted
time: 2ms
memory: 12500kb
input:
okkkkkok okokkkoo kookooko
output:
0 9 0 8
result:
ok 4 number(s): "0 9 0 8"
Test #20:
score: 0
Accepted
time: 5ms
memory: 11600kb
input:
ccc cpppp cc
output:
3 1 3 3
result:
ok 4 number(s): "3 1 3 3"
Test #21:
score: 0
Accepted
time: 18ms
memory: 12124kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 11ms
memory: 11240kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 2ms
memory: 12940kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 1ms
memory: 12632kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 4ms
memory: 12496kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 5ms
memory: 12960kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: 0
Accepted
time: 1ms
memory: 11800kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 907 0 906
result:
ok 4 number(s): "748 907 0 906"
Test #28:
score: 0
Accepted
time: 1ms
memory: 12344kb
input:
kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #29:
score: 0
Accepted
time: 4ms
memory: 12032kb
input:
illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #30:
score: 0
Accepted
time: 20ms
memory: 12904kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1 702 0 701
result:
ok 4 number(s): "1 702 0 701"
Test #31:
score: 0
Accepted
time: 6ms
memory: 11636kb
input:
mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...
output:
374 454 0 906
result:
ok 4 number(s): "374 454 0 906"
Test #32:
score: 0
Accepted
time: 2ms
memory: 12292kb
input:
kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...
output:
291 370 50 788
result:
ok 4 number(s): "291 370 50 788"
Test #33:
score: 0
Accepted
time: 9ms
memory: 11804kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
937 966 0 965
result:
ok 4 number(s): "937 966 0 965"
Test #34:
score: 0
Accepted
time: 10ms
memory: 12628kb
input:
apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...
output:
35 64 600 663
result:
ok 4 number(s): "35 64 600 663"
Test #35:
score: 0
Accepted
time: 4ms
memory: 11568kb
input:
msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...
output:
0 966 0 965
result:
ok 4 number(s): "0 966 0 965"
Test #36:
score: 0
Accepted
time: 5ms
memory: 12356kb
input:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...
output:
1 768 0 767
result:
ok 4 number(s): "1 768 0 767"
Test #37:
score: 0
Accepted
time: 1ms
memory: 11512kb
input:
jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...
output:
468 483 0 964
result:
ok 4 number(s): "468 483 0 964"
Test #38:
score: 0
Accepted
time: 7ms
memory: 11796kb
input:
dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...
output:
429 443 80 964
result:
ok 4 number(s): "429 443 80 964"
Test #39:
score: -100
Time Limit Exceeded
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...