QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360946#5256. InsertionszaaWA 3ms17872kbC++143.1kb2024-03-22 16:23:022024-03-22 16:23:02

Judging History

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

  • [2024-03-22 16:23:02]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:17872kb
  • [2024-03-22 16:23:02]
  • 提交

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 s){
    for(;x<=k;x+=lowbit(x)) w[x]+=s;
}
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: 3ms
memory: 17872kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

ok 4 number(s): "2 2 6 7"

Test #2:

score: 0
Accepted
time: 3ms
memory: 17828kb

input:

z
zzkkzzkk
z

output:

5 2 0 1

result:

ok 4 number(s): "5 2 0 1"

Test #3:

score: 0
Accepted
time: 3ms
memory: 17784kb

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: 17816kb

input:

q
uuquu
u

output:

4 2 0 1

result:

ok 4 number(s): "4 2 0 1"

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 17832kb

input:

gpgggpppg
pg
gpgg

output:

2 2 1 4

result:

wrong answer 2nd numbers differ - expected: '1', found: '2'