QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724302#7748. Karshilov's Matching Problem IIucup-team5217ML 1ms3824kbC++233.2kb2024-11-08 11:52:032024-11-08 11:52:04

Judging History

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

  • [2024-11-08 11:52:04]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3824kb
  • [2024-11-08 11:52:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ld=long double;
struct Zbox{
    vector<int> box;
    string s;
    void intt(string _s){
        s=_s;int sz=s.size();
        box.resize(sz);
        box[0]=sz;
        for(int i=1,l=-1,r=-1;i<sz;i++){
            box[i]=0;
            if(i<=r)    box[i]=min(box[i-l],r-i+1);
            if(box[i]+i-1<r)    continue;
            else {
                while(box[i]+i<sz&&s[box[i]+i]==s[box[i]])  box[i]++;
                l=i,r=box[i]+i-1;
            }
        }
    }
    void intt_lcp_pre(string _s,Zbox x){
        s=_s;
        int s1=s.size(),s2=x.s.size();
        box.resize(s1);
        for(int i=0,l=-1,r=-1;i<s1;i++){
            box[i]=0;
            if(i<=r)    box[i]=min(x.box[i-l],r-i+1);
            if(box[i]+i-1<r)    continue;
            else{
                while(box[i]<s2&&i+box[i]<s1&&s[i+box[i]]==x.s[box[i]]) box[i]++;
                l=i,r=box[i]+i-1;
            }
        }
    }
};
using ll = long long;
void solve(void) {
    int n,q;
    cin>>n>>q;
    string s,t;cin>>s>>t;
    Zbox sbox;sbox.intt(s);
    Zbox tbox;tbox.intt_lcp_pre(t,sbox);
    vector<ll> w(n);
    vector<ll> prew(n);
    vector<ll> presum(n);
    for(int i=0;i<n;i++)    cin>>w[i];
    for(int i=0;i<n;i++)    if(i==0)    prew[i]=w[i];else prew[i]=prew[i-1]+w[i];
    for(int i=0;i<n;i++){
        ll res=(tbox.box[i]==0?0:prew[tbox.box[i]-1]);
        if(i==0)    presum[i]=res;
        else presum[i]=presum[i-1]+res;
    }


    vector<ll> pre_res_s(n,0);
    vector<ll> nxtw(n,0);
    vector<int> nxt(n,0);nxt[0]=-1;pre_res_s[0]=w[0];
    for(int i=1,j=-1;i<n;i++){
        while(j!=-1&&s[i]!=s[j+1])  j=nxt[j];
        if(s[i]==s[j+1])    j++;
        nxt[i]=j;
        pre_res_s[i]=w[i]+(i==0?0:pre_res_s[i-1]);
        if(j!=-1){
            pre_res_s[i]+=nxtw[nxt[i]]+w[j];
            nxtw[i]=nxtw[nxt[i]]+w[j];
        }
    }



    vector<int> info(n);
    for(int i=0;i<n;i++)    info[i]=i+tbox.box[i]-1;
    vector<int> mx(n<<2+10);
    auto build=[&](auto self,int p,int l,int r)->void {
        if(l==r)    {mx[p]=info[l];return ;}
        int mid=(l+r)>>1;
        self(self,p<<1,l,mid);
        self(self,p<<1|1,mid+1,r);
        mx[p]=max(mx[p<<1],mx[p<<1|1]);
    };
    build(build,1,0,n-1);
    auto query=[&](auto self,int p,int l,int r,int L,int R,int maxn)->int {
        if(l==r)    return mx[p]>maxn?l:-1;
        int mid=(l+r)>>1;
        if(mid>=R)  return self(self,p<<1,l,mid,L,R,maxn);
        else if(mid<L)  return self(self,p<<1|1,mid+1,r,L,R,maxn);
        if(mid>=L&&mx[p<<1]>maxn){
            int w=self(self,p<<1,l,mid,L,R,maxn);
            if(w!=-1)   return w;
        }
        return self(self,p<<1|1,mid+1,r,L,R,maxn);
    };
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;l--,r--;
        int w=query(query,1,0,n-1,l,r,r);
        if(w==-1)   cout<<(presum[r]-(l==0?0:presum[l-1]))<<'\n';
        else{
            ll ans=((w==0?0:presum[w-1])-(l==0?0:presum[l-1]))+pre_res_s[r-w];
            cout<<ans<<'\n';
        }
    }

}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int _ = 1;
    while (_--) solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3824kb

input:

8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8

output:

1
3
3
16
38

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

15 4
heheheheehhejie
heheheheheheheh
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
2 3
4 8
2 6
1 15

output:

3
13
13
174

result:

ok 4 lines

Test #3:

score: -100
Memory Limit Exceeded

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

108147037823514
221878585246974
455339807727642
440286198422821
148115747906237
88695249853257
351159618462315
58850354020997
65824434822005
270158033672354
197732558443069
298193894693053
239511187032650
28139154231325
408380171835227
268053430937402
32417121185965
104813548228675
44074926058619
78...

result: