#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 == '~' ? 5 : v == 'U' ? 4 : v == 'G' ? 3 : v == 'C' ? 2 : v == 'A';
}
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, V2;
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];
V.push_back({p + "#", i});
V.push_back({p + "~", i});
}
auto sort_level = [&](int p) {
V2.resize(V.size());
vector<int> Fr(6, 0);
for(auto &[w, id] : V) {
++Fr[(w.size() <= p) ? 0 : sort_id(w[p])];
}
for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
reverse(V.begin(), V.end());
for(auto it : V)
V2[--Fr[(it.first.size() <= p) ? 0 : sort_id(it.first[p])]] = it;
V = move(V2);
V2.clear();
};
for(int i = len_ma; i >= 0; --i)
sort_level(i);
int nrw = 0;
for(auto &[w, id] : V) {
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 lambda function:
selling_rna.cpp:84:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | ++Fr[(w.size() <= p) ? 0 : sort_id(w[p])];
| ~~~~~~~~~^~~~
selling_rna.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
| ~~^~~~~~~~~~~
selling_rna.cpp:89:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | V2[--Fr[(it.first.size() <= p) ? 0 : sort_id(it.first[p])]] = it;
| ~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
22268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1603 ms |
40160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
40124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
22268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
