#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mod = 712271227;
const int p = 7;
const int mxn = 1e5+10;
const int mxm = 2e6+10;
const int B = sqrt(mxm);
int pw[mxm];
basic_string<int> base[mxn];
basic_string<int> pref[mxn];
basic_string<int> suf[mxn];
pair<string,string> req[mxn];
pii qhash[mxn];
int N,Q;
int ans[mxn];
basic_string<ll> prec[B+1][B+1];
vector<pii> vs;
inline int mad(int a,int b){
a += b;
return a>=mod?a-mod:a;
}
inline int mub(int a,int b){
return mad(a,mod-b);
}
inline int mul(int a,int b){
return 1ll*a*b%mod;
}
void process(int id){
auto &s = base[id];
int n = s.size();
pref[id] = suf[id] = basic_string<int>(n,0);
pref[id][0] = suf[id].back() = 0;
for(int i = 0;i<n;i++){
if(i){
pref[id][i] = pref[id][i-1];
suf[id][n-1-i] = suf[id][n-1-i+1];
}
pref[id][i] = mad(pref[id][i],mul(s[i],pw[i]));
suf[id][n-1-i] = mad(suf[id][n-1-i],mul(s[n-1-i],pw[i]));
}
for(int i = 1;i<=min(B,n);i++){
for(int j = 1;j<=min(B,n);j++){
ll val = 1ll*pref[id][i-1]*mod+suf[id][n-j];
prec[i][j] += val;
}
}
return;
}
void makereq(int id){
auto &[l,r] = req[id];
int n = l.size();
for(int i = 0;i<n;i++){
qhash[id].fs = mad(qhash[id].fs,mul(l[i],pw[i]));
}
n = r.size();
for(int i = n-1;i>=0;i--){
qhash[id].sc = mad(qhash[id].sc,mul(r[i],pw[n-1-i]));
}
return;
}
void big(int ls,int rs,int lh,int rh){
int b = max(ls,rs);
auto pos = lower_bound(vs.begin(),vs.end(),pii(max(ls,rs),-1))-vs.begin();
int ans = 0;
for(int i = pos;i<vs.size();i++){
int now = vs[i].sc;
int n = base[now].size();
if(n<max(ls,rs))continue;
if(pref[now][ls-1] == lh&&suf[now][n-rs] == rh)ans++;
}
cout<<ans<<'\n';
return;
}
void small(int ls,int rs,int lh,int rh){
ll tar = 1ll*lh*mod+rh;
auto lp = lower_bound(prec[ls][rs].begin(),prec[ls][rs].end(),tar)-prec[ls][rs].begin();
auto rp = upper_bound(prec[ls][rs].begin(),prec[ls][rs].end(),tar)-prec[ls][rs].begin();
cout<<(rp-lp)<<'\n';
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>Q;
pw[0] = 1;
for(int i = 1;i<mxn;i++)pw[i] = mul(pw[i-1],p);
for(int i = 1;i<=N;i++){
string s1;
cin>>s1;
for(auto &j:s1){
int tmp;
if(j == 'A')tmp = 1;
else if(j == 'C')tmp = 2;
else if(j == 'G')tmp = 3;
else tmp = 4;
base[i] += tmp;
}
vs.push_back(pii((int)base[i].size(),i));
process(i);
}
for(int i = 1;i<=Q;i++){
string s1,s2;
cin>>s1>>s2;
for(auto &j:s1){
int tmp;
if(j == 'A')tmp = 1;
else if(j == 'C')tmp = 2;
else if(j == 'G')tmp = 3;
else tmp = 4;
req[i].fs += tmp;
}
for(auto &j:s2){
int tmp;
if(j == 'A')tmp = 1;
else if(j == 'C')tmp = 2;
else if(j == 'G')tmp = 3;
else tmp = 4;
req[i].sc += tmp;
}
makereq(i);
}
sort(vs.begin(),vs.end());
for(int i = 1;i<=B;i++)for(int j = 1;j<=B;j++)sort(prec[i][j].begin(),prec[i][j].end());
for(int i = 1;i<=Q;i++){
auto &[l,r] = req[i];
if(l.size()>B||r.size()>B)big(l.size(),r.size(),qhash[i].fs,qhash[i].sc);
else small(l.size(),r.size(),qhash[i].fs,qhash[i].sc);
}
}
Compilation message
selling_rna.cpp: In function 'void big(int, int, int, int)':
selling_rna.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = pos;i<vs.size();i++){
| ~^~~~~~~~~~
selling_rna.cpp:77:6: warning: unused variable 'b' [-Wunused-variable]
77 | int b = max(ls,rs);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
79440 KB |
Output is correct |
| 2 |
Correct |
26 ms |
79520 KB |
Output is correct |
| 3 |
Correct |
26 ms |
79608 KB |
Output is correct |
| 4 |
Correct |
25 ms |
79600 KB |
Output is correct |
| 5 |
Correct |
26 ms |
79452 KB |
Output is correct |
| 6 |
Correct |
25 ms |
79452 KB |
Output is correct |
| 7 |
Correct |
25 ms |
79540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1598 ms |
676764 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
83376 KB |
Output is correct |
| 2 |
Correct |
64 ms |
89532 KB |
Output is correct |
| 3 |
Correct |
63 ms |
87408 KB |
Output is correct |
| 4 |
Correct |
41 ms |
84272 KB |
Output is correct |
| 5 |
Correct |
64 ms |
89548 KB |
Output is correct |
| 6 |
Correct |
64 ms |
87376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
79440 KB |
Output is correct |
| 2 |
Correct |
26 ms |
79520 KB |
Output is correct |
| 3 |
Correct |
26 ms |
79608 KB |
Output is correct |
| 4 |
Correct |
25 ms |
79600 KB |
Output is correct |
| 5 |
Correct |
26 ms |
79452 KB |
Output is correct |
| 6 |
Correct |
25 ms |
79452 KB |
Output is correct |
| 7 |
Correct |
25 ms |
79540 KB |
Output is correct |
| 8 |
Execution timed out |
1598 ms |
676764 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
