QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360934#5256. InsertionszaaWA 8ms37040kbC++143.1kb2024-03-22 16:15:082024-03-22 16:15:09

Judging History

你现在查看的是最新测评结果

  • [2024-03-22 16:15:09]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:37040kb
  • [2024-03-22 16:15:08]
  • 提交

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'