#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
int get(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
return 3;
}
struct Trie{
struct Node{
int nxt[4];
int l, r;
Node(){
memset(nxt, -1, sizeof(nxt));
l = 1e9, r = -1;
}
};
vector<Node> tr;
int cur = 0;
Trie(){
tr.push_back(Node());
}
int new_node(){
tr.push_back(Node());
++cur;
return cur;
}
void add_string(string &s, int id){
int p = 0;
for(int i = 0; i < sz(s); ++i){
tr[p].l = min(tr[p].l, id);
tr[p].r = max(tr[p].r, id);
int c = get(s[i]);
if(tr[p].nxt[c] == -1)
tr[p].nxt[c] = new_node();
p = tr[p].nxt[c];
}
tr[p].l = min(tr[p].l, id);
tr[p].r = max(tr[p].r, id);
}
pii get_range(string &s){
int p = 0;
for(int i = 0; i < sz(s); ++i){
int c = get(s[i]);
if(tr[p].nxt[c] == -1)
return {-1, -1};
p = tr[p].nxt[c];
}
return {tr[p].l, tr[p].r};
}
};
struct ReversedTrie{
struct Node{
int nxt[4];
vector<int> ids;
Node(){
memset(nxt, -1, sizeof(nxt));
}
};
vector<Node> tr;
int cur = 0;
ReversedTrie(){
tr.push_back(Node());
}
int new_node(){
tr.push_back(Node());
++cur;
return cur;
}
void add_string(string &s, int id){
int p = 0;
for(int i = 0; i < sz(s); ++i){
tr[p].ids.push_back(id);
int c = get(s[i]);
if(tr[p].nxt[c] == -1)
tr[p].nxt[c] = new_node();
p = tr[p].nxt[c];
}
tr[p].ids.push_back(id);
}
void init(){
for(int i = 0; i <= cur; ++i)
sort(all(tr[cur].ids));
}
int query(string &s, int l, int r){
int p = 0;
for(int i = 0; i < sz(s); ++i){
int c = get(s[i]);
if(tr[p].nxt[c] == -1)
return 0;
p = tr[p].nxt[c];
}
int lv = lower_bound(all(tr[p].ids), l) - tr[p].ids.begin();
int rv = upper_bound(all(tr[p].ids), r) - tr[p].ids.begin() - 1;
return rv - lv + 1;
}
};
const int N = 1e5 + 3;
int n, m;
string s[N];
Trie trie;
ReversedTrie rtrie;
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> s[i];
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; ++i){
trie.add_string(s[i], i);
reverse(all(s[i]));
}
for(int i = 1; i <= n; ++i)
rtrie.add_string(s[i], i);
while(m--){
string p, q;
cin >> p >> q;
reverse(all(q));
pii rn = trie.get_range(p);
cout << rtrie.query(q, rn.F, rn.S) << '\n';
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
#define task "troll"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
#ifdef LOCAL
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
return 0;
}
Compilation message
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3416 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3416 KB |
Output is correct |
5 |
Correct |
1 ms |
3416 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
144276 KB |
Output is correct |
2 |
Correct |
174 ms |
140812 KB |
Output is correct |
3 |
Correct |
70 ms |
66896 KB |
Output is correct |
4 |
Correct |
76 ms |
65432 KB |
Output is correct |
5 |
Correct |
146 ms |
158112 KB |
Output is correct |
6 |
Correct |
146 ms |
160164 KB |
Output is correct |
7 |
Correct |
44 ms |
19028 KB |
Output is correct |
8 |
Correct |
134 ms |
87912 KB |
Output is correct |
9 |
Correct |
118 ms |
84700 KB |
Output is correct |
10 |
Correct |
90 ms |
86440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
4568 KB |
Output is correct |
2 |
Correct |
19 ms |
4788 KB |
Output is correct |
3 |
Correct |
18 ms |
4824 KB |
Output is correct |
4 |
Correct |
14 ms |
4820 KB |
Output is correct |
5 |
Correct |
15 ms |
4724 KB |
Output is correct |
6 |
Correct |
19 ms |
4824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3416 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3416 KB |
Output is correct |
5 |
Correct |
1 ms |
3416 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
172 ms |
144276 KB |
Output is correct |
9 |
Correct |
174 ms |
140812 KB |
Output is correct |
10 |
Correct |
70 ms |
66896 KB |
Output is correct |
11 |
Correct |
76 ms |
65432 KB |
Output is correct |
12 |
Correct |
146 ms |
158112 KB |
Output is correct |
13 |
Correct |
146 ms |
160164 KB |
Output is correct |
14 |
Correct |
44 ms |
19028 KB |
Output is correct |
15 |
Correct |
134 ms |
87912 KB |
Output is correct |
16 |
Correct |
118 ms |
84700 KB |
Output is correct |
17 |
Correct |
90 ms |
86440 KB |
Output is correct |
18 |
Correct |
19 ms |
4568 KB |
Output is correct |
19 |
Correct |
19 ms |
4788 KB |
Output is correct |
20 |
Correct |
18 ms |
4824 KB |
Output is correct |
21 |
Correct |
14 ms |
4820 KB |
Output is correct |
22 |
Correct |
15 ms |
4724 KB |
Output is correct |
23 |
Correct |
19 ms |
4824 KB |
Output is correct |
24 |
Correct |
165 ms |
123444 KB |
Output is correct |
25 |
Correct |
178 ms |
123236 KB |
Output is correct |
26 |
Correct |
158 ms |
123452 KB |
Output is correct |
27 |
Correct |
81 ms |
57756 KB |
Output is correct |
28 |
Correct |
127 ms |
36100 KB |
Output is correct |
29 |
Correct |
56 ms |
12356 KB |
Output is correct |