#include <bits/stdc++.h>
using namespace std;
inline int in() {
int result = 0;
char ch = getchar_unlocked();
while (true) {
if(ch >= '0' && ch <= '9')
break;
ch = getchar_unlocked();
}
result = ch-'0';
while(true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result*10 + (ch - '0');
}
return result;
}
inline void ins(string &s) {
char c=getchar_unlocked();
while(c>='A'&&c<='Z') {
s=s+c;
c=getchar_unlocked();
}
}
inline void out(int x) {
int rev=x, count = 0;
if(x == 0) {
putchar_unlocked('0');
putchar_unlocked('\n');
return;
}
while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
rev = 0;
while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
while(count--)
putchar_unlocked('0');
putchar_unlocked('\n');
}
const int mxN1=1e5, mxN2=2e6;
int n, m, enc[256], ans[mxN1], ft[mxN2+1];
string ss[mxN1];
vector<int> pts[mxN2];
struct query {
int i, l, r, w;
};
vector<query> queries[mxN2+1];
struct trie {
int sz=1, c[mxN2][4], dt, st[mxN2], en[mxN2];
inline void ins(string &s) {
for(int i=0, u=0; i<s.size(); ++i) {
if(!c[u][enc[s[i]]])
c[u][enc[s[i]]]=sz++;
u=c[u][enc[s[i]]];
}
}
inline void dfs1(int u=0) {
st[u]=dt++;
for(int i=0; i<4; ++i)
if(c[u][i])
dfs1(c[u][i]);
en[u]=dt;
}
inline int gi(string &s) {
int u=0;
for(int i=0; i<s.size(); u=c[u][enc[s[i]]], ++i)
if(!c[u][enc[s[i]]])
return -1;
return u;
}
} t[2];
inline void upd(int i, int x) {
for(++i; i<=mxN2; i+=i&-i)
ft[i]+=x;
}
inline int qry(int i) {
int r=0;
for(; i; i-=i&-i)
r+=ft[i];
return r;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
enc['A']=0;
enc['G']=1;
enc['C']=2;
enc['U']=3;
n=in(), m=in();
for(int i=0; i<n; ++i) {
ins(ss[i]);
t[0].ins(ss[i]);
reverse(ss[i].begin(), ss[i].end());
t[1].ins(ss[i]);
}
t[0].dfs1();
t[1].dfs1();
for(int i=0; i<n; ++i) {
int y=t[1].st[t[1].gi(ss[i])];
reverse(ss[i].begin(), ss[i].end());
int x=t[0].st[t[0].gi(ss[i])];
pts[y].push_back(x);
}
for(int i=0; i<m; ++i) {
string p, q;
ins(p), ins(q), reverse(q.begin(), q.end());
int pi=t[0].gi(p), qi=t[1].gi(q);
if(pi==-1||qi==-1)
continue;
queries[t[1].st[qi]].push_back({i, t[0].st[pi], t[0].en[pi], -1});
queries[t[1].en[qi]].push_back({i, t[0].st[pi], t[0].en[pi], 1});
}
for(int i=0; i<mxN2; ++i) {
for(int x : pts[i])
upd(x, 1);
for(query q : queries[i+1])
ans[q.i]+=q.w*(qry(q.r)-qry(q.l));
}
for(int i=0; i<m; ++i)
out(ans[i]);
}
Compilation message
selling_rna.cpp: In member function 'void trie::ins(std::__cxx11::string&)':
selling_rna.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0, u=0; i<s.size(); ++i) {
~^~~~~~~~~
selling_rna.cpp:67:21: warning: array subscript has type 'char' [-Wchar-subscripts]
if(!c[u][enc[s[i]]])
^
selling_rna.cpp:68:18: warning: array subscript has type 'char' [-Wchar-subscripts]
c[u][enc[s[i]]]=sz++;
^
selling_rna.cpp:69:19: warning: array subscript has type 'char' [-Wchar-subscripts]
u=c[u][enc[s[i]]];
^
selling_rna.cpp: In member function 'int trie::gi(std::__cxx11::string&)':
selling_rna.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<s.size(); u=c[u][enc[s[i]]], ++i)
~^~~~~~~~~
selling_rna.cpp:81:43: warning: array subscript has type 'char' [-Wchar-subscripts]
for(int i=0; i<s.size(); u=c[u][enc[s[i]]], ++i)
^
selling_rna.cpp:82:21: warning: array subscript has type 'char' [-Wchar-subscripts]
if(!c[u][enc[s[i]]])
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
97528 KB |
Output is correct |
| 2 |
Correct |
99 ms |
97640 KB |
Output is correct |
| 3 |
Correct |
96 ms |
97640 KB |
Output is correct |
| 4 |
Correct |
98 ms |
97680 KB |
Output is correct |
| 5 |
Correct |
98 ms |
97920 KB |
Output is correct |
| 6 |
Correct |
103 ms |
97920 KB |
Output is correct |
| 7 |
Correct |
94 ms |
97928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1471 ms |
152376 KB |
Output is correct |
| 2 |
Correct |
1389 ms |
154196 KB |
Output is correct |
| 3 |
Execution timed out |
1536 ms |
167276 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
167276 KB |
Output is correct |
| 2 |
Correct |
112 ms |
167276 KB |
Output is correct |
| 3 |
Correct |
113 ms |
167276 KB |
Output is correct |
| 4 |
Correct |
109 ms |
167276 KB |
Output is correct |
| 5 |
Correct |
111 ms |
167276 KB |
Output is correct |
| 6 |
Correct |
111 ms |
167276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
97528 KB |
Output is correct |
| 2 |
Correct |
99 ms |
97640 KB |
Output is correct |
| 3 |
Correct |
96 ms |
97640 KB |
Output is correct |
| 4 |
Correct |
98 ms |
97680 KB |
Output is correct |
| 5 |
Correct |
98 ms |
97920 KB |
Output is correct |
| 6 |
Correct |
103 ms |
97920 KB |
Output is correct |
| 7 |
Correct |
94 ms |
97928 KB |
Output is correct |
| 8 |
Correct |
1471 ms |
152376 KB |
Output is correct |
| 9 |
Correct |
1389 ms |
154196 KB |
Output is correct |
| 10 |
Execution timed out |
1536 ms |
167276 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
