#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
int n, m;
string str[N];
string s[N], e[N];
int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
struct Trie {
bool pass;
int nwt[N << 3][4], ma[N << 3], mi[N << 3], sz[N << 3], it;
Trie() {
memset(mi, 63, sizeof mi);
}
void clear() {
memset(nwt, 0, sizeof nwt);
memset(ma, 0, sizeof ma);
it = 0;
pass = true;
}
void add(const auto& s, const int& node) {
int g = 0;
for (int i = 1; i <= s.size(); ++i) {
int path = convert(s[i - 1]);
if (!nwt[g][path]) nwt[g][path] = ++it;
g = nwt[g][path];
ma[g] = max(ma[g], node);
mi[g] = min(mi[g], node);
sz[g] += pass;
}
}
pair<int, int> que(const auto& s) {
int g = 0;
for (int i = 1; i <= s.size(); ++i) {
int path = convert(s[i - 1]);
if (!nwt[g][path]) return {0, 0};
g = nwt[g][path];
}
return {pass ? sz[g] : mi[g], ma[g]};
}
} T;
vector<int> l[N], r[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> str[i];
for (int i = 1; i <= m; ++i) cin >> s[i] >> e[i];
for (int i = 1; i <= n; ++i) T.add(str[i], i);
for (int i = 1; i <= m; ++i) {
reverse(e[i].begin(), e[i].end());
const auto& [st, ed] = (T.que(s[i]));
if (st) l[st - 1].push_back(i);
r[ed].push_back(i);
}
T.clear();
vector<int> answer(m + 1);
for (int i = 1; i <= n; ++i) {
T.add(string(str[i].rbegin(), str[i].rend()), i);
for (const auto& j : l[i]) answer[j] -= T.que(e[j]).first;
for (const auto& j : r[i]) answer[j] += T.que(e[j]).first;
}
for (int i = 1; i <= m; ++i) cout << answer[i] << "\n";
}
Compilation message
selling_rna.cpp:10:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
10 | int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
| ^~~~
selling_rna.cpp:27:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
27 | void add(const auto& s, const int& node) {
| ^~~~
selling_rna.cpp:40:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
40 | pair<int, int> que(const auto& s) {
| ^~~~
selling_rna.cpp: In instantiation of 'void Trie::add(const auto:24&, const int&) [with auto:24 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:62:47: required from here
selling_rna.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 1; i <= s.size(); ++i) {
| ~~^~~~~~~~~~~
selling_rna.cpp: In instantiation of 'std::pair<int, int> Trie::que(const auto:25&) [with auto:25 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:65:39: required from here
selling_rna.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 1; i <= s.size(); ++i) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
36440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
86100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
37972 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
37484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
36440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
