#include <bits/stdc++.h>
using namespace std;
struct T {
int nxt[4] = {-1, -1, -1, -1};
vector<int> id;
};
int mapuj(char x)
{
if(x == 'A') {
return 0;
}
if(x == 'G') {
return 1;
}
if(x == 'C') {
return 2;
}
if(x == 'U') {
return 3;
}
}
struct tree {
vector<T> trie;
tree() { trie.emplace_back(); }
void insert(string &s, int i)
{
int v = 0;
for(char x : s) {
int id = mapuj(x);
if(trie[v].nxt[id] == -1) {
trie[v].nxt[id] = (int)trie.size();
trie.emplace_back();
}
trie[v].id.emplace_back(i);
v = trie[v].nxt[id];
}
trie[v].id.emplace_back(i);
}
int search(string &s)
{
int v = 0;
for(char x : s) {
int id = mapuj(x);
if(trie[v].nxt[id] == -1) {
return -1;
}
v = trie[v].nxt[id];
}
return v;
}
};
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<string> s(n + 1);
for(int i = 1; i <= n; i++) {
cin >> s[i];
}
sort(1 + s.begin(), s.end());
tree trie, trierev;
for(int i = 1; i <= n; ++i) {
trie.insert(s[i], i);
reverse(s[i].begin(), s[i].end());
trierev.insert(s[i], i);
}
for(int i = 1; i <= q; i++) {
string pre, suf;
cin >> pre >> suf;
int one = trie.search(pre);
reverse(suf.begin(), suf.end());
int two = trierev.search(suf);
if(one == -1 || two == -1) {
cout << 0 << '\n';
continue;
}
vector<int> &wek1 = trie.trie[one].id;
vector<int> &wek2 = trierev.trie[two].id;
int lo = wek1.front(), hi = wek1.back();
auto it1 = lower_bound(wek2.begin(), wek2.end(), lo);
auto it2 = upper_bound(wek2.begin(), wek2.end(), hi);
if(it1 == wek2.end() || hi < *it1) {
cout << 0 << '\n';
continue;
}
cout << distance(it1, it2) << '\n';
}
}
Compilation message
selling_rna.cpp: In function 'int mapuj(char)':
selling_rna.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
24 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
152764 KB |
Output is correct |
2 |
Correct |
231 ms |
145324 KB |
Output is correct |
3 |
Correct |
234 ms |
151100 KB |
Output is correct |
4 |
Correct |
230 ms |
144004 KB |
Output is correct |
5 |
Correct |
271 ms |
191504 KB |
Output is correct |
6 |
Correct |
289 ms |
191320 KB |
Output is correct |
7 |
Correct |
57 ms |
19668 KB |
Output is correct |
8 |
Correct |
238 ms |
126740 KB |
Output is correct |
9 |
Correct |
219 ms |
113320 KB |
Output is correct |
10 |
Correct |
175 ms |
109376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
3940 KB |
Output is correct |
2 |
Correct |
23 ms |
3288 KB |
Output is correct |
3 |
Correct |
26 ms |
3764 KB |
Output is correct |
4 |
Correct |
17 ms |
3224 KB |
Output is correct |
5 |
Correct |
20 ms |
3284 KB |
Output is correct |
6 |
Correct |
24 ms |
3724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
238 ms |
152764 KB |
Output is correct |
9 |
Correct |
231 ms |
145324 KB |
Output is correct |
10 |
Correct |
234 ms |
151100 KB |
Output is correct |
11 |
Correct |
230 ms |
144004 KB |
Output is correct |
12 |
Correct |
271 ms |
191504 KB |
Output is correct |
13 |
Correct |
289 ms |
191320 KB |
Output is correct |
14 |
Correct |
57 ms |
19668 KB |
Output is correct |
15 |
Correct |
238 ms |
126740 KB |
Output is correct |
16 |
Correct |
219 ms |
113320 KB |
Output is correct |
17 |
Correct |
175 ms |
109376 KB |
Output is correct |
18 |
Correct |
31 ms |
3940 KB |
Output is correct |
19 |
Correct |
23 ms |
3288 KB |
Output is correct |
20 |
Correct |
26 ms |
3764 KB |
Output is correct |
21 |
Correct |
17 ms |
3224 KB |
Output is correct |
22 |
Correct |
20 ms |
3284 KB |
Output is correct |
23 |
Correct |
24 ms |
3724 KB |
Output is correct |
24 |
Correct |
235 ms |
127188 KB |
Output is correct |
25 |
Correct |
243 ms |
127352 KB |
Output is correct |
26 |
Correct |
236 ms |
125888 KB |
Output is correct |
27 |
Correct |
215 ms |
125900 KB |
Output is correct |
28 |
Correct |
166 ms |
39996 KB |
Output is correct |
29 |
Correct |
75 ms |
14944 KB |
Output is correct |