QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267568#7748. Karshilov's Matching Problem IIAlishWA 78ms41276kbC++172.2kb2023-11-27 14:36:242023-11-27 14:36:25

Judging History

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

  • [2024-08-25 20:42:18]
  • hack成功,自动添加数据
  • (/hack/789)
  • [2023-11-27 14:36:25]
  • 评测
  • 测评结果:WA
  • 用时:78ms
  • 内存:41276kb
  • [2023-11-27 14:36:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);


ll mod = 1e9+7;

const int N = 3e5+23;
string s, t;
ll w[N];
int LPS[N];
int z[N];
ll prefz[N];
ll prefkmp[N];
ll prefpref[N];
ll prefw[N];
int n, m;
vector<pii> Q[N];
int ans[N];
vector<int> out[N];
set<int>st;


int main()
{
    fast_io
    cin>>n>>m;
    cin>>s>>t;
    s=s+'#'+t;
    for (int i=1; i<=n; i++) cin>>w[i];
    for (int i=1; i<=n; i++) prefw[i]=prefw[i-1]+w[i];

    for (int i=1, j=0; i<n; i++){
        while(j>0 && s[i]!=s[j])j=LPS[j-1];
        if(s[j]==s[i]) j++;
        LPS[i]=j;
    }

    int Mx=0, ind=0;
    for (int i=1; i<s.size(); i++){
        if(Mx>i) z[i]=min(Mx-i, z[i-ind]);
        while(z[i]+i<s.size() && s[z[i]+i]==s[z[i]])z[i]++;
        if(z[i]>Mx){
            Mx=z[i];
            ind=i;
        }
    }
    for (int i=n; i<=2*n; i++) prefz[i]=prefz[i-1]+prefw[z[i]];
    for (int i=0; i<n; i++){
        prefpref[i+1]=w[i+1]+prefpref[LPS[i]];
        prefkmp[i+1]=prefpref[i+1]+prefkmp[i];
    }
    for (int i=n; i<=2*n; i++){
        if(z[i]) {
            st.insert(i);
            out[z[i]+i].pb(i);
        }
    }

    for (int i=0; i<m; i++){
        int l, r; cin>>l>>r; l+=n; r+=n;
        Q[r].pb({l, i});
    }

    for (int i=n; i<=2*n; i++){

        for (int j: out[i]) st.erase(j);
        for (auto pp: Q[i]){
            int l=pp.F, ind=pp.S;
            auto x=st.lower_bound(l);
            if(x==st.end() || *x>i){
                ans[ind]=prefz[i]-prefz[l-1];
                continue;
            }
            ans[ind]=prefz[*x-1]-prefz[l-1]+prefkmp[i-*x+1];
        }
    }
    for (int i=0; i<m; i++) cout<<ans[i]<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 20768kb

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: 0ms
memory: 23920kb

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
Wrong Answer
time: 78ms
memory: 41276kb

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

-238689766
574735614
259907610
510975269
-494263619
-119776439
-1202625941
712131205
-233956491
295786658
854069821
-1389700931
-1959196086
-1471492067
1796429659
227026746
-1291964243
-833662909
-28332933
1521598991
-210103850
888469404
604921440
813327493
-853316457
1964711175
-669853735
-13877485...

result:

wrong answer 1st lines differ - expected: '108147037823514', found: '-238689766'