#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;
int bit[3000000];
void add(int k,int x){
k++;
while(k<3000000){
bit[k]+=x;
k+=k&-k;
}
}
int sum(int k){
int res=0;
while(k){
res+=bit[k];
k-=k&-k;
}
return res;
}
int sum(int l,int r){
return sum(r)-sum(l);
}
int getId(char c){
if(c=='A')return 0;
if(c=='G')return 1;
if(c=='C')return 2;
return 3;
}
struct node{
node*nx[4];
int l,r;
}pool[3000000];
node*root1=&pool[0],*root2=&pool[1];
int pointer=2;
node*add(node*root,string&s){
node*x=root;
for(char c:s){
if(x->nx[getId(c)]==NULL){
x->nx[getId(c)]=&pool[pointer++];
}
x=x->nx[getId(c)];
}
return x;
}
int cnt=0;
void dfs(node*t){
t->l=cnt++;
rep(i,4){
if(t->nx[i])dfs(t->nx[i]);
}
t->r=cnt+1;
}
char S[200000];
string s[200000],p[200000],q[200000];
struct st{
int ty,l,r;
};
vector<st>query[3000000];
int ans[200000];
int main(){
int n,m;scanf("%d%d",&n,&m);
rep(i,n){
scanf("%s",S);
s[i]=S;
add(root1,s[i]);
reverse(s[i].begin(),s[i].end());
add(root2,s[i]);
reverse(s[i].begin(),s[i].end());
}
rep(i,m){
scanf("%s",S);p[i]=S;
scanf("%s",S);q[i]=S;
add(root1,p[i]);
reverse(q[i].begin(),q[i].end());
add(root2,q[i]);
}
dfs(root1);
dfs(root2);
vector<st>v;
rep(i,m){
node*a=add(root1,p[i]),*b=add(root2,q[i]);
query[a->l].push_back({i,b->l,b->r});
query[a->r].push_back({i+m,b->l,b->r});
}
rep(i,n){
int a=add(root1,s[i])->l;
reverse(s[i].begin(),s[i].end());
int b=add(root2,s[i])->l;
reverse(s[i].begin(),s[i].end());
query[a].push_back({-1,b,b+1});
}
rep(i,3000000){
for(auto&s:query[i]){
if(s.ty>=0){
int res=sum(s.l,s.r);
if(s.ty<m)ans[s.ty]-=res;
else ans[s.ty-m]+=res;
}
else{
add(s.l,1);
}
}
}
rep(i,m){
printf("%d\n",ans[i]);
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:74:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n,m;scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
selling_rna.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",S);
~~~~~^~~~~~~~
selling_rna.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",S);p[i]=S;
~~~~~^~~~~~~~
selling_rna.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",S);q[i]=S;
~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
89740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
179544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
92924 KB |
Output is correct |
| 2 |
Incorrect |
118 ms |
91868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
89740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
