QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#267568 | #7748. Karshilov's Matching Problem II | Alish | WA | 78ms | 41276kb | C++17 | 2.2kb | 2023-11-27 14:36:24 | 2023-11-27 14:36:25 |
Judging History
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'