#include <bits/stdc++.h>
#define MAX 25005000
int N,Q;
using ll = long long;
const ll MOD = 998244353;
typedef std::array<std::array<ll,2>,2> matriz;
matriz mul(matriz a,matriz b){
matriz c={};
for(int i=0;i!=2;++i){
for(int j=0;j!=2;++j){
for(int k=0;k!=2;++k){
c[i][j]=(c[i][j]+(a[i][k]*b[k][j]))%MOD;
}
}
}
return c;
}
int get_num(char ch){
switch(ch){
case 'A': return 0;
case 'G': return 1;
case 'C': return 2;
case 'U': return 3;
}
}
int filhos[MAX][4];
int valor[5005000];
std::string str[5005000];
int freq[MAX];
int cur=2;
int alocar(void){
if(cur==MAX){
std::cout<<"oops\n";
exit(0);
}
return cur++;
}
void explora(std::deque<char> dek,std::string bet){
int inicio = 1;
while(dek.size()){
int& ref = filhos[inicio][get_num(dek.front())];
if(!ref)ref=alocar();
inicio=ref;
dek.pop_front();
}
freq[inicio]++;
assert(inicio<5005000);
str[inicio]=bet;
}
std::deque<char> gera_dek(std::string s){
std::deque<char> dek;
for(auto&x:s)dek.push_back(x);
return dek;
}
matriz neutro;
matriz gera_mat(int B){
matriz c={};
c[0][0]=7;
c[1][0]=B+2;
c[1][1]=1;
return c;
}
int mat[5005000*4];
std::string alvo;
void update(int t,int b,int la=0,int ra=MAX-1,int pos=1){
if(!mat[pos])mat[pos]=alocar();
{
int inicio = mat[pos];
for(int i=0;i!=alvo.size();++i){
auto&ref=filhos[inicio][get_num(alvo[i])];
if(!ref)ref=alocar();
freq[inicio]+=b;
inicio=ref;
}
freq[inicio]+=b;
}
if(la==ra)return;
int m = (la+ra)/2;
if(t<=m)
update(t,b,la,m,pos*2);
if(t>m)
update(t,b,m+1,ra,(pos*2)+1);
}
std::string analisa;
int query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
if(ra<l||la>r)return 0;
if(la>=l&&ra<=r){
if(!mat[pos])return 0;
int inicio = mat[pos];
for(int i=0;i!=analisa.size();++i){
auto&ref=filhos[inicio][get_num(analisa[i])];
if(!ref)return 0;
inicio=ref;
}
return freq[inicio];
}
int m = (la+ra)/2;
return query(l,r,la,m,pos*2) + query(l,r,m+1,ra,(pos*2)+1);
}
int tamanhos[MAX];
int cur2=1;
int dfs(int node){
if(!node)return 0;
assert(!valor[node]);
assert(cur2<5005000&&node<5005000);
valor[node]=cur2;
int size=1;
if(freq[node]){///Opa!!!
alvo=str[node];
std::reverse(alvo.begin(),alvo.end());
update(cur2,freq[node]);
}
++cur2;
for(int i=0;i!=4;++i){
size+=dfs(filhos[node][i]);
}
tamanhos[node]=size;
return size;
}
int main()
{
neutro[0][0]=neutro[1][1]=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N >> Q;
for(int i=0;i!=N;++i){
std::string s;
std::cin >> s;
explora(gera_dek(s),s);
}
dfs(1);
///Processa
for(int i=0;i!=Q;++i){
std::string l,r;
std::cin >> l >> r;
int inicio = 1;
for(int i=0;i!=l.size();++i){
int p = get_num(l[i]);
inicio = filhos[inicio][p];
if(!inicio){
std::cout<<"0\n";
goto prox;
}
}
{
int tam = tamanhos[inicio],pos=valor[inicio];
analisa=r;std::reverse(analisa.begin(),analisa.end());
int soma = query(pos,pos+tam-1);
std::cout<<soma<<"\n";
}
prox:{}
}
}
Compilation message
selling_rna.cpp: In function 'void update(int, int, int, int, int)':
selling_rna.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0;i!=alvo.size();++i){
| ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(int, int, int, int, int)':
selling_rna.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i=0;i!=analisa.size();++i){
| ~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0;i!=l.size();++i){
| ~^~~~~~~~~~
selling_rna.cpp: In function 'int get_num(char)':
selling_rna.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
25 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
157132 KB |
Output is correct |
| 2 |
Correct |
76 ms |
157096 KB |
Output is correct |
| 3 |
Correct |
71 ms |
157196 KB |
Output is correct |
| 4 |
Correct |
70 ms |
157132 KB |
Output is correct |
| 5 |
Correct |
71 ms |
157216 KB |
Output is correct |
| 6 |
Correct |
70 ms |
157200 KB |
Output is correct |
| 7 |
Correct |
75 ms |
157132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
439 ms |
648636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
157400 KB |
Output is correct |
| 2 |
Correct |
92 ms |
159744 KB |
Output is correct |
| 3 |
Correct |
112 ms |
158592 KB |
Output is correct |
| 4 |
Correct |
90 ms |
157260 KB |
Output is correct |
| 5 |
Correct |
100 ms |
158580 KB |
Output is correct |
| 6 |
Correct |
99 ms |
158028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
157132 KB |
Output is correct |
| 2 |
Correct |
76 ms |
157096 KB |
Output is correct |
| 3 |
Correct |
71 ms |
157196 KB |
Output is correct |
| 4 |
Correct |
70 ms |
157132 KB |
Output is correct |
| 5 |
Correct |
71 ms |
157216 KB |
Output is correct |
| 6 |
Correct |
70 ms |
157200 KB |
Output is correct |
| 7 |
Correct |
75 ms |
157132 KB |
Output is correct |
| 8 |
Incorrect |
439 ms |
648636 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
