#include <bits/stdc++.h>
using namespace std;
const int LimitNM = 1e5;
const int LimitTrie = 1.5e6;
const int BUFFER = 1e9;
using Point = pair<int, int>;
int n, m, CharId[2310], QueryAns[LimitNM + 5];
Point RNATrieId[LimitNM + 5], QuerySuffixEuler[LimitNM + 5];
string s[LimitNM + 5];
vector<Point> Axis;
struct Trie {
int cnt, nxt[LimitTrie][4], Eulercnt, In[LimitTrie], Out[LimitTrie];
Trie() { cnt = Eulercnt = 0; }
int TrieAdd(string& x, bool IsRNA) {
int root = 0;
for (int i = 0; i < x.size(); i++) {
if (nxt[root][CharId[x[i]]] == 0)
if (IsRNA) nxt[root][CharId[x[i]]] = ++cnt;
else return 0;
root = nxt[root][CharId[x[i]]];
}
return root;
}
void dfsEulerTour(int root) {
In[root] = ++Eulercnt;
for (int i = 0; i < 4; i++) {
if (nxt[root][i] == 0)
continue;
dfsEulerTour(nxt[root][i]);
}
Out[root] = Eulercnt;
}
} PrefixTrie, SuffixTrie;
int BIT[LimitTrie];
void BITAdd(int pos) {
while (pos <= SuffixTrie.Eulercnt) {
BIT[pos]++;
pos += (pos & (-pos));
}
}
int BITGetPre(int pos) {
int Total = 0;
while (pos > 0) {
Total += BIT[pos];
pos -= (pos & (-pos));
}
return Total;
}
int BITGetRange(int l, int r) {
if (l > r) return 0;
return BITGetPre(r) - BITGetPre(l - 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
vector<char> CharList = {'A', 'G', 'C', 'U'};
for (int i = 0; i < 4; i++)
CharId[CharList[i]] = i;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
RNATrieId[i].first = PrefixTrie.TrieAdd(s[i], true);
reverse(s[i].begin(), s[i].end());
RNATrieId[i].second = SuffixTrie.TrieAdd(s[i], true);
}
PrefixTrie.dfsEulerTour(0);
SuffixTrie.dfsEulerTour(0);
for (int i = 1; i <= n; i++) {
RNATrieId[i].first = PrefixTrie.In[RNATrieId[i].first];
RNATrieId[i].second = SuffixTrie.In[RNATrieId[i].second];
Axis.push_back(RNATrieId[i]);
}
// s[i] = {prefixid, suffixid}, prefixtrie = {in, out}, suffixtrie = {in, out}
for (int i = 1; i <= m; i++) {
string p, q;
cin >> p >> q;
Point NonEulerId;
NonEulerId.first = PrefixTrie.TrieAdd(p, false);
reverse(q.begin(), q.end());
NonEulerId.second = SuffixTrie.TrieAdd(q, false);
if (min(NonEulerId.first, NonEulerId.second) == 0) continue;
Axis.emplace_back(PrefixTrie.In[NonEulerId.first], -i);
Axis.emplace_back(PrefixTrie.Out[NonEulerId.first], i + BUFFER);
QuerySuffixEuler[i] = {SuffixTrie.In[NonEulerId.second], SuffixTrie.Out[NonEulerId.second]};
}
sort(Axis.begin(), Axis.end());
// cout << "RNATRIEID\n";
// for (int i = 1; i <= n; i++) {
// cout << RNATrieId[i].first << " " << RNATrieId[i].second << '\n';
// }
// cout << '\n';
// for (auto& c : Axis) {
// if (c.second < 0) cout <<"Qin"<< c.first << ", " << -c.second << '\n';
// else if (c.second > BUFFER) cout <<"Qout"<< c.first << " " << c.second - BUFFER << '\n';
// else cout << c.first << " " << c.second << '\n';
// }
// for (int i = 1; i <= m; i++) {
// cout << QuerySuffixEuler[i].first << ", " << QuerySuffixEuler[i].second << '\n';
// }
// cout << "spec " << SuffixTrie.In[SuffixTrie.nxt[0][1]] << " " << SuffixTrie.Out[SuffixTrie.nxt[0][1]] << '\n';
for (auto& c : Axis) {
if (c.second < 0) {
QueryAns[-c.second] -= BITGetRange(QuerySuffixEuler[-c.second].first, QuerySuffixEuler[-c.second].second);
} else if (c.second > BUFFER) {
QueryAns[c.second - BUFFER] += BITGetRange(QuerySuffixEuler[c.second - BUFFER].first, QuerySuffixEuler[c.second - BUFFER].second);
} else {
BITAdd(c.second);
}
}
for (int i = 1; i <= m; i++)
cout << QueryAns[i] << '\n';
}
Compilation message
selling_rna.cpp: In member function 'int Trie::TrieAdd(std::string&, bool)':
selling_rna.cpp:16:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
selling_rna.cpp:17:38: warning: array subscript has type 'char' [-Wchar-subscripts]
17 | if (nxt[root][CharId[x[i]]] == 0)
| ^
selling_rna.cpp:18:49: warning: array subscript has type 'char' [-Wchar-subscripts]
18 | if (IsRNA) nxt[root][CharId[x[i]]] = ++cnt;
| ^
selling_rna.cpp:17:16: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
17 | if (nxt[root][CharId[x[i]]] == 0)
| ^
selling_rna.cpp:20:41: warning: array subscript has type 'char' [-Wchar-subscripts]
20 | root = nxt[root][CharId[x[i]]];
| ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:58:27: warning: array subscript has type 'char' [-Wchar-subscripts]
58 | CharId[CharList[i]] = i;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
1 ms |
16888 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16892 KB |
Output is correct |
| 5 |
Correct |
1 ms |
16732 KB |
Output is correct |
| 6 |
Correct |
1 ms |
16732 KB |
Output is correct |
| 7 |
Correct |
1 ms |
16732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
99 ms |
110676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19720 KB |
Output is correct |
| 2 |
Correct |
14 ms |
18596 KB |
Output is correct |
| 3 |
Correct |
16 ms |
18904 KB |
Output is correct |
| 4 |
Correct |
12 ms |
18652 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18392 KB |
Output is correct |
| 6 |
Correct |
17 ms |
18844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
1 ms |
16888 KB |
Output is correct |
| 4 |
Correct |
2 ms |
16892 KB |
Output is correct |
| 5 |
Correct |
1 ms |
16732 KB |
Output is correct |
| 6 |
Correct |
1 ms |
16732 KB |
Output is correct |
| 7 |
Correct |
1 ms |
16732 KB |
Output is correct |
| 8 |
Runtime error |
99 ms |
110676 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
