#include <bits/stdc++.h>
#define MN 100071
using namespace std;
int n, m;
static inline int nr_lit(const char &v) {
return v == 'U' ? 3 : v == 'G' ? 2 : v == 'C';
}
static inline int sort_id(const char &v) {
return v == '~' ? 6 : v == 'U' ? 5 : v == 'G' ? 4 : v == 'C' ? 3 : v == 'A' ? 2 : v == '#';
}
struct trie {
struct nod {
int nr;
nod* fii[4];
};
using ns = nod*;
ns root;
trie() {
root = new nod{0, {0, 0, 0, 0}};
}
void add(const string &word) {
ns p = root;
p->nr++;
for(auto it : word) {
if(!p->fii[nr_lit(it)]) {
p->fii[nr_lit(it)] = new nod{0, {0, 0, 0, 0}};
}
p = p->fii[nr_lit(it)];
p->nr++;
}
}
int count(const string &word) {
ns p = root;
for(auto it : word)
if(!p->fii[nr_lit(it)]) return 0;
else p = p->fii[nr_lit(it)];
return p->nr;
}
};
namespace AINT {
trie V[4 * MN];
void add_string(int p, string &v, int u = 1, int s = 1, int d = n) {
if(d < p || p < s) return;
V[u].add(v);
if(s == d) return;
add_string(p, v, u << 1, s, (s + d) >> 1);
add_string(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
}
int query(int l, int r, string &v, int u = 1, int s = 1, int d = n) {
if(r < s || d < l) return 0;
if(l <= s && d <= r) return V[u].count(v);
return query(l, r, v, u << 1, s, (s + d) >> 1) + query(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int len_ma = 0;
cin >> n >> m;
vector<pair<string, int> > V;
for(int i = 1; i <= n; ++i) {
string v;
cin >> v; len_ma = max(len_ma, (int)v.size());
v += '#';
V.push_back({v, -1});
}
vector<int> R(m), St(m), Dr(m);
vector<string> Q(m);
for(int i = 0; i < m; ++i) {
string p;
cin >> p >> Q[i];
len_ma = max(len_ma, int(p.size()));
V.push_back({p + "$", i});
V.push_back({p + "~", i});
}
vector<int> OrdV, O2;
for(int i = 0; i < V.size(); ++i) OrdV.push_back(i);
auto sort_level = [&](int p) {
O2.resize(V.size());
vector<int> Fr(7, 0);
for(auto &it : OrdV)
++Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])];
for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
reverse(OrdV.begin(), OrdV.end());
for(auto &it : OrdV)
O2[--Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])]] = it;
swap(O2, OrdV);
};
for(int i = len_ma; i >= 0; --i)
sort_level(i);
int nrw = 0;
for(auto it : OrdV) {
auto &[w, id] = V[it];
if(id == -1) {
w.resize(w.size() - 1);
reverse(w.begin(), w.end());
AINT::add_string(++nrw, w);
}
else {
if(!St[id]) St[id] = nrw + 1;
Dr[id] = nrw;
}
}
for(int i = 0; i < m; ++i) {
reverse(Q[i].begin(), Q[i].end());
R[i] = AINT::query(St[i], Dr[i], Q[i]);
}
for(auto it : R) cout << it << "\n";
return 0;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i = 0; i < V.size(); ++i) OrdV.push_back(i);
| ~~^~~~~~~~~~
selling_rna.cpp: In lambda function:
selling_rna.cpp:87:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
87 | ++Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])];
| ~~~~~~~~~~~~~~~~~~~^~~~
selling_rna.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
| ~~^~~~~~~~~~~
selling_rna.cpp:91:41: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
91 | O2[--Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])]] = it;
| ~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
22228 KB |
Output is correct |
| 2 |
Correct |
20 ms |
22356 KB |
Output is correct |
| 3 |
Correct |
28 ms |
22348 KB |
Output is correct |
| 4 |
Correct |
17 ms |
22232 KB |
Output is correct |
| 5 |
Correct |
16 ms |
22312 KB |
Output is correct |
| 6 |
Correct |
17 ms |
22272 KB |
Output is correct |
| 7 |
Correct |
17 ms |
22268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1436 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
41408 KB |
Output is correct |
| 2 |
Correct |
92 ms |
41264 KB |
Output is correct |
| 3 |
Correct |
114 ms |
41576 KB |
Output is correct |
| 4 |
Correct |
76 ms |
38212 KB |
Output is correct |
| 5 |
Correct |
95 ms |
38960 KB |
Output is correct |
| 6 |
Correct |
94 ms |
40540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
22228 KB |
Output is correct |
| 2 |
Correct |
20 ms |
22356 KB |
Output is correct |
| 3 |
Correct |
28 ms |
22348 KB |
Output is correct |
| 4 |
Correct |
17 ms |
22232 KB |
Output is correct |
| 5 |
Correct |
16 ms |
22312 KB |
Output is correct |
| 6 |
Correct |
17 ms |
22272 KB |
Output is correct |
| 7 |
Correct |
17 ms |
22268 KB |
Output is correct |
| 8 |
Runtime error |
1436 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
