QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360934 | #5256. Insertions | zaa | WA | 8ms | 37040kb | C++14 | 3.1kb | 2024-03-22 16:15:08 | 2024-03-22 16:15:09 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
string s,t,p;
int n,m,k;
int a,b;
int sum;
int nxt[N];
int idx,dfn[N],ed[N];
int w[N],ans[N];
bool vis[N];
vector<int> g1[N],g2[N];
vector<pair<int,int> > e[N];
struct node{
string s,t,p;
int nxt[N],v[N];
int w[N],g[N];
inline int KMP(){
int o=0;
for(int i=2;i<=k;i++){
while(o&&p[i]!=p[o+1]) o=nxt[o];
if(p[i]==p[o+1]) o++;
nxt[i]=o;
}
o=0;
for(int i=1;i<=m;i++){
while(o&&t[i]!=p[o+1]) o=nxt[o];
if(t[i]==p[o+1]) o++;
if(o==k){
sum++;
o=nxt[o];
}
}
return o;
}
inline void cal(bool z){
for(int i=1;i<=k;i++) w[i]=w[nxt[i]]+v[k-i];
int res=0,o=0;
for(int i=0;i<=n;i++){
while(o&&s[i]!=p[o+1]) o=nxt[o];
if(s[i]==p[o+1]) o++;
g[i]=o;
if(o==k) res++;
if(!z) ans[i]+=res+w[o];
else ans[n-i]+=res+w[o];
if(o==k) o=nxt[o];
}
}
}A,B;
inline int lowbit(int x){
return (x&(-x));
}
inline void add(int x,int k){
for(;x<=n;x+=lowbit(x)) w[x]+=k;
}
inline int Sum(int x){
int res=0;
for(;x;x-=lowbit(x)) res+=w[x];
return res;
}
void dfs1(int x){
dfn[x]=++idx;
for(int i:g2[x]) dfs1(i);
ed[x]=idx;
}
void dfs2(int x){
bool z=0;
if(x&&vis[x+m]&&k-x-m){
add(dfn[k-x-m],1);
add(ed[k-x-m]+1,-1);
z=1;
}
for(pair<int,int> i:e[x]) ans[i.second]+=Sum(dfn[i.first]);
for(int i:g1[x]) dfs2(i);
if(z){
add(dfn[k-x-m],-1);
add(ed[k-x-m]+1,1);
}
}
signed main(){
cin>>s>>t>>p;
n=s.size();m=t.size();k=p.size();
A.s=' '+s;A.t=' '+t;A.p=' '+p;
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
reverse(p.begin(),p.end());
B.s=' '+s;B.t=' '+t;B.p=' '+p;
a=A.KMP();b=B.KMP();
sum/=2;
while(a){
B.v[a]++;
a=A.nxt[a];
}
while(b){
A.v[b]++;
b=B.nxt[b];
}
A.cal(0);B.cal(1);
if(m<k){
int o=0;
for(int i=2;i<=m;i++){
while(o&&A.t[i]!=A.t[o+1]) o=nxt[o];
if(A.t[i]==A.t[o+1]) o++;
nxt[i]=o;
}
o=0;
for(int i=1;i<=k;i++){
while(o&&A.p[i]!=A.t[o+1]) o=nxt[o];
if(A.p[i]==A.t[o+1]) o++;
if(o==m){
vis[i]=1;
o=nxt[o];
}
}
for(int i=1;i<=k;i++){
g1[A.nxt[i]].push_back(i);
g2[B.nxt[i]].push_back(i);
}
dfs1(0);
for(int i=0;i<=n;i++){
int l=A.g[i],r=B.g[n-i];
if(l&&r) e[l].push_back({r,i});
}
dfs2(0);
}
int l=0,r=0,mx=0,res=0;
for(int i=0;i<=n;i++){
if(ans[i]>mx){
l=i;r=i;
mx=ans[i];
res=0;
}
if(ans[i]==mx) res++,r=i;
}
printf("%lld %lld %lld %lld",mx+sum,res,l,r);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32448kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 5ms
memory: 22204kb
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: 32448kb
input:
wgwwggggw g gggg
output:
2 5 4 8
result:
ok 4 number(s): "2 5 4 8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 26592kb
input:
q uuquu u
output:
4 2 0 1
result:
ok 4 number(s): "4 2 0 1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 30484kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 26336kb
input:
p xpxp p
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 36564kb
input:
aacaacacaa ca caca
output:
2 5 2 9
result:
ok 4 number(s): "2 5 2 9"
Test #8:
score: 0
Accepted
time: 3ms
memory: 26664kb
input:
k kekekkekk k
output:
7 2 0 1
result:
ok 4 number(s): "7 2 0 1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 30496kb
input:
ghhhhg g ghhg
output:
2 1 3 3
result:
ok 4 number(s): "2 1 3 3"
Test #10:
score: 0
Accepted
time: 3ms
memory: 26316kb
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: 32508kb
input:
nddnnndndn dnd ndndn
output:
3 1 5 5
result:
ok 4 number(s): "3 1 5 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 26384kb
input:
imiimmmm miimi i
output:
6 9 0 8
result:
ok 4 number(s): "6 9 0 8"
Test #13:
score: 0
Accepted
time: 0ms
memory: 30460kb
input:
gzzzzzzzzz zgzzzg gzgggzzz
output:
0 11 0 10
result:
ok 4 number(s): "0 11 0 10"
Test #14:
score: 0
Accepted
time: 3ms
memory: 24560kb
input:
m mmwmwmw wwmww
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 26264kb
input:
jmmmmjmmj jmjjjmjm mjmmmmjj
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #16:
score: 0
Accepted
time: 4ms
memory: 28404kb
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: 28452kb
input:
plpll llplll pppppppl
output:
0 6 0 5
result:
ok 4 number(s): "0 6 0 5"
Test #18:
score: 0
Accepted
time: 4ms
memory: 26324kb
input:
yypppypyy ppyyypppy ypyppypp
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #19:
score: 0
Accepted
time: 0ms
memory: 26408kb
input:
okkkkkok okokkkoo kookooko
output:
0 9 0 8
result:
ok 4 number(s): "0 9 0 8"
Test #20:
score: 0
Accepted
time: 0ms
memory: 28296kb
input:
ccc cpppp cc
output:
3 1 3 3
result:
ok 4 number(s): "3 1 3 3"
Test #21:
score: 0
Accepted
time: 8ms
memory: 37040kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 3ms
memory: 32564kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 0ms
memory: 30768kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 3ms
memory: 30484kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 0ms
memory: 36732kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 2ms
memory: 30552kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: 0
Accepted
time: 3ms
memory: 32984kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 907 0 906
result:
ok 4 number(s): "748 907 0 906"
Test #28:
score: 0
Accepted
time: 0ms
memory: 30936kb
input:
kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #29:
score: 0
Accepted
time: 0ms
memory: 32464kb
input:
illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #30:
score: -100
Wrong Answer
time: 3ms
memory: 32592kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1 676 0 675
result:
wrong answer 2nd numbers differ - expected: '702', found: '676'