#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
struct A
{
int nxt[5];
int con=0;
int len;
int l,r;
}Node[5][2000005];
struct B
{
int l,r;
int nxl,nxr;
int nxt;
int con;
}Node2[20000005];
vector < vector < int > > all[5];
vector < int > xx[5];
pair < int , int > where[100005];
char ttt[100005];
int sz[100005];
int cha[505];
int now[5]={1,1};
int tt[5]={0,0};
int now2=1,N;
int con;
void New(int x,int y,int z)
{
Node[x][y].con=0;
Node[x][y].nxt[0]=-1;
Node[x][y].nxt[1]=-1;
Node[x][y].nxt[2]=-1;
Node[x][y].nxt[3]=-1;
Node[x][y].len=z;
}
void build(int x,int y,int here)
{
if(Node[x][here].len==sz[y])
{
Node[x][here].con++;
return;
}
if(Node[x][here].nxt[all[x][y][Node[x][here].len]]==-1)
{
Node[x][here].nxt[all[x][y][Node[x][here].len]]=now[x]++;
New(x,Node[x][here].nxt[all[x][y][Node[x][here].len]],Node[x][here].len+1);
}
build(x,y,Node[x][here].nxt[all[x][y][Node[x][here].len]]);
}
void BFS(int x,int here)
{
int i;
Node[x][here].l=tt[x];
Node[x][here].r=tt[x]+Node[x][here].con-1;
tt[x]+=Node[x][here].con;
for(i=0;i<4;i++)
{
if(Node[x][here].nxt[i]!=-1)
{
BFS(x,Node[x][here].nxt[i]);
Node[x][here].r=Node[x][Node[x][here].nxt[i]].r;
}
}
}
pair < int , int > Find(int x,int here)
{
if(Node[x][here].len==con) return make_pair(Node[x][here].l,Node[x][here].r);
if(Node[x][here].nxt[xx[0][Node[x][here].len]]==-1) return make_pair(-1,-1);
return Find(x,Node[x][here].nxt[xx[0][Node[x][here].len]]);
}
void New2(int l,int r,int nxt,int here)
{
Node2[here].l=l;
Node2[here].r=r;
Node2[here].nxt=nxt;
Node2[here].nxl=-1;
Node2[here].nxr=-1;
Node2[here].con=0;
}
void add(int x,int y,int here)
{
//printf("%d %d %d %d %d %d\n",x,y,here,Node2[here].l,Node2[here].r,Node2[here].nxt);
Node2[here].con++;
if(Node2[here].nxt==-2)
{
if(y==Node2[here].l&&y==Node2[here].r) return ;
if(y<=(Node2[here].l+Node2[here].r)/2)
{
if(Node2[here].nxl==-1)
{
Node2[here].nxl=now2++;
New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-2,Node2[here].nxl);
}
add(x,y,Node2[here].nxl);
}
else
{
if(Node2[here].nxr==-1)
{
Node2[here].nxr=now2++;
New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-2,Node2[here].nxr);
}
add(x,y,Node2[here].nxr);
}
}
else
{
if(Node2[here].nxt==-1)
{
Node2[here].nxt=now2++;
New2(0,N,-2,Node2[here].nxt);
}
add(x,y,Node2[here].nxt);
if(x==Node2[here].l&&x==Node2[here].r) return;
if(x<=(Node2[here].l+Node2[here].r)/2)
{
if(Node2[here].nxl==-1)
{
Node2[here].nxl=now2++;
New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-1,Node2[here].nxl);
}
add(x,y,Node2[here].nxl);
}
else
{
if(Node2[here].nxr==-1)
{
Node2[here].nxr=now2++;
New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-1,Node2[here].nxr);
}
add(x,y,Node2[here].nxr);
}
}
}
int main()
{
pair < int , int > a,b;
int M,K,t=0,i,j,k,t2,ans=0;
cha['A']=0;
cha['U']=1;
cha['C']=2;
cha['G']=3;
scanf("%d %d",&N,&M);
New2(0,N,-1,0);
New(0,0,0);
New(1,0,0);
for(i=0;i<N;i++)
{
scanf("%s",ttt);
sz[i]=strlen(ttt);
xx[0].clear();
for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
xx[1].clear();
for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
all[0].push_back(xx[0]);
all[1].push_back(xx[1]);
build(0,i,0);
build(1,i,0);
}
BFS(0,0);
BFS(1,0);
for(i=0;i<N;i++)
{
con=sz[i];
xx[0]=all[0][i];
where[i].first=Find(0,0).first;
xx[0]=all[1][i];
where[i].second=Find(1,0).first;
add(where[i].first,where[i].second,0);
}
while(M--)
{
scanf("%s",ttt);
xx[0].clear();
con=strlen(ttt);
for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
a=Find(0,0);
scanf("%s",ttt);
xx[0].clear();
con=strlen(ttt);
for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
b=Find(1,0);
if(a.first==-1||b.first==-1) printf("0\n");
else
{
ans=0;
for(i=0;i<N;i++)
{
if(a.first<=where[i].first&&where[i].first<=a.second)
{
if(b.first<=where[i].second&&where[i].second<=b.second) ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:166:55: warning: array subscript has type 'char' [-Wchar-subscripts]
166 | for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
| ~~~~~^
selling_rna.cpp:168:63: warning: array subscript has type 'char' [-Wchar-subscripts]
168 | for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
| ~~~~~~~~~~~~~^
selling_rna.cpp:191:53: warning: array subscript has type 'char' [-Wchar-subscripts]
191 | for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
| ~~~~~^
selling_rna.cpp:196:59: warning: array subscript has type 'char' [-Wchar-subscripts]
196 | for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
| ~~~~~~~~~~~^
selling_rna.cpp:152:11: warning: unused variable 'K' [-Wunused-variable]
152 | int M,K,t=0,i,j,k,t2,ans=0;
| ^
selling_rna.cpp:152:13: warning: unused variable 't' [-Wunused-variable]
152 | int M,K,t=0,i,j,k,t2,ans=0;
| ^
selling_rna.cpp:152:21: warning: unused variable 'k' [-Wunused-variable]
152 | int M,K,t=0,i,j,k,t2,ans=0;
| ^
selling_rna.cpp:152:23: warning: unused variable 't2' [-Wunused-variable]
152 | int M,K,t=0,i,j,k,t2,ans=0;
| ^~
selling_rna.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
157 | scanf("%d %d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
163 | scanf("%s",ttt);
| ~~~~~^~~~~~~~~~
selling_rna.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
188 | scanf("%s",ttt);
| ~~~~~^~~~~~~~~~
selling_rna.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
193 | scanf("%s",ttt);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
352748 KB |
Output is correct |
| 2 |
Correct |
171 ms |
352748 KB |
Output is correct |
| 3 |
Correct |
170 ms |
352748 KB |
Output is correct |
| 4 |
Correct |
172 ms |
352776 KB |
Output is correct |
| 5 |
Correct |
173 ms |
352748 KB |
Output is correct |
| 6 |
Correct |
173 ms |
352620 KB |
Output is correct |
| 7 |
Correct |
171 ms |
352620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
401 ms |
372744 KB |
Output is correct |
| 2 |
Correct |
509 ms |
379372 KB |
Output is correct |
| 3 |
Correct |
448 ms |
375404 KB |
Output is correct |
| 4 |
Correct |
498 ms |
379244 KB |
Output is correct |
| 5 |
Correct |
481 ms |
375148 KB |
Output is correct |
| 6 |
Correct |
475 ms |
375348 KB |
Output is correct |
| 7 |
Correct |
326 ms |
366700 KB |
Output is correct |
| 8 |
Correct |
507 ms |
379952 KB |
Output is correct |
| 9 |
Correct |
489 ms |
378604 KB |
Output is correct |
| 10 |
Correct |
392 ms |
377068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1566 ms |
359380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
352748 KB |
Output is correct |
| 2 |
Correct |
171 ms |
352748 KB |
Output is correct |
| 3 |
Correct |
170 ms |
352748 KB |
Output is correct |
| 4 |
Correct |
172 ms |
352776 KB |
Output is correct |
| 5 |
Correct |
173 ms |
352748 KB |
Output is correct |
| 6 |
Correct |
173 ms |
352620 KB |
Output is correct |
| 7 |
Correct |
171 ms |
352620 KB |
Output is correct |
| 8 |
Correct |
401 ms |
372744 KB |
Output is correct |
| 9 |
Correct |
509 ms |
379372 KB |
Output is correct |
| 10 |
Correct |
448 ms |
375404 KB |
Output is correct |
| 11 |
Correct |
498 ms |
379244 KB |
Output is correct |
| 12 |
Correct |
481 ms |
375148 KB |
Output is correct |
| 13 |
Correct |
475 ms |
375348 KB |
Output is correct |
| 14 |
Correct |
326 ms |
366700 KB |
Output is correct |
| 15 |
Correct |
507 ms |
379952 KB |
Output is correct |
| 16 |
Correct |
489 ms |
378604 KB |
Output is correct |
| 17 |
Correct |
392 ms |
377068 KB |
Output is correct |
| 18 |
Execution timed out |
1566 ms |
359380 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
