#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e5 + 5;
int getval(char s){
if (s == 'A') return 0;
else if (s == 'G') return 1;
else if (s == 'C') return 2;
else return 3;
}
char getchar(int c){
if (c == 0) return 'A';
else if (c == 1) return 'G';
else if (c == 2) return 'C';
else if (c == 3) return 'U';
}
struct Trie{
struct Node{
int l, r;
Node *a[4];
Node(){
l = (int)1e9;
r = (int)-1e9;
for (int i = 0; i <= 3; ++i)
a[i] = NULL;
}
};
Node *root = new Node();
void add(string &s, int id){
Node *p = root;
for (int i = 0; i < s.size(); ++i){
int c = getval(s[i]);
if (p->a[c] == NULL) p->a[c] = new Node();
p = p->a[c];
p->l = min(p->l, id);
p->r = max(p->r, id);
}
}
pair<int, int> getrange(string &s){
Node *p = root;
for (int i = 0; i < s.size(); ++i){
int c = getval(s[i]);
if (p->a[c] == NULL) return {0, 0};
p = p->a[c];
}
return {p->l, p->r};
}
};
struct RevTrie{
struct Node{
Node *a[4];
vector<int> h;
Node(){
for (int i = 0; i <= 3; ++i)
a[i] = NULL;
}
};
Node *root = new Node();
void add(string &s, int id){
reverse(s.begin(), s.end());
Node *p = root;
for (int i = 0; i < s.size(); ++i){
int c = getval(s[i]);
if (p->a[c] == NULL) p->a[c] = new Node();
p = p->a[c];
p->h.pb(id);
}
}
int match(string &s, pair<int, int> range){
reverse(s.begin(), s.end());
Node *p = root;
for (int i = 0; i < s.size(); ++i){
int c = getval(s[i]);
if (p->a[c] == NULL) return 0;
p = p->a[c];
}
int small = lower_bound(p->h.begin(), p->h.end(), range.fi) - p->h.begin() - 1;
int large = upper_bound(p->h.begin(), p->h.end(), range.se) - p->h.begin() - 1;
return large - small;
}
};
int n, m;
string s[N], p, q;
Trie trie1;
RevTrie trie2;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> s[i];
}
sort(s + 1, s + 1 + n);
for (int i = 1; i <= n; ++i){
trie1.add(s[i], i);
trie2.add(s[i], i);
}
while(m--){
cin >> p >> q;
cout << trie2.match(q, trie1.getrange(p)) << "\n";
}
return 0;
}
Compilation message
selling_rna.cpp: In member function 'void Trie::add(std::string&, int)':
selling_rna.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < s.size(); ++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::getrange(std::string&)':
selling_rna.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < s.size(); ++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void RevTrie::add(std::string&, int)':
selling_rna.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i < s.size(); ++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int RevTrie::match(std::string&, std::pair<int, int>)':
selling_rna.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int i = 0; i < s.size(); ++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'char getchar(int)':
selling_rna.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
20 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
1 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
2 ms |
3416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
195 ms |
194228 KB |
Output is correct |
2 |
Correct |
197 ms |
184316 KB |
Output is correct |
3 |
Correct |
127 ms |
111904 KB |
Output is correct |
4 |
Correct |
128 ms |
107092 KB |
Output is correct |
5 |
Correct |
208 ms |
178848 KB |
Output is correct |
6 |
Correct |
188 ms |
181260 KB |
Output is correct |
7 |
Correct |
44 ms |
19028 KB |
Output is correct |
8 |
Correct |
203 ms |
117828 KB |
Output is correct |
9 |
Correct |
138 ms |
101460 KB |
Output is correct |
10 |
Correct |
100 ms |
96116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
4816 KB |
Output is correct |
2 |
Correct |
15 ms |
5172 KB |
Output is correct |
3 |
Correct |
17 ms |
4704 KB |
Output is correct |
4 |
Correct |
13 ms |
4444 KB |
Output is correct |
5 |
Correct |
15 ms |
4700 KB |
Output is correct |
6 |
Correct |
18 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
1 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
2 ms |
3416 KB |
Output is correct |
8 |
Correct |
195 ms |
194228 KB |
Output is correct |
9 |
Correct |
197 ms |
184316 KB |
Output is correct |
10 |
Correct |
127 ms |
111904 KB |
Output is correct |
11 |
Correct |
128 ms |
107092 KB |
Output is correct |
12 |
Correct |
208 ms |
178848 KB |
Output is correct |
13 |
Correct |
188 ms |
181260 KB |
Output is correct |
14 |
Correct |
44 ms |
19028 KB |
Output is correct |
15 |
Correct |
203 ms |
117828 KB |
Output is correct |
16 |
Correct |
138 ms |
101460 KB |
Output is correct |
17 |
Correct |
100 ms |
96116 KB |
Output is correct |
18 |
Correct |
27 ms |
4816 KB |
Output is correct |
19 |
Correct |
15 ms |
5172 KB |
Output is correct |
20 |
Correct |
17 ms |
4704 KB |
Output is correct |
21 |
Correct |
13 ms |
4444 KB |
Output is correct |
22 |
Correct |
15 ms |
4700 KB |
Output is correct |
23 |
Correct |
18 ms |
4700 KB |
Output is correct |
24 |
Correct |
182 ms |
160696 KB |
Output is correct |
25 |
Correct |
238 ms |
160872 KB |
Output is correct |
26 |
Correct |
188 ms |
158640 KB |
Output is correct |
27 |
Correct |
112 ms |
94032 KB |
Output is correct |
28 |
Correct |
124 ms |
38740 KB |
Output is correct |
29 |
Correct |
71 ms |
12004 KB |
Output is correct |