This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |