#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
struct fenwick_tree {
vector<long long> bit;
int n;
fenwick_tree(int _n) : n(_n) {
bit.assign(n + 7, 0);
}
long long get(int i) const {
long long res = 0;
for (minimize(i, n); i > 0; i -= i & -i) res += bit[i];
return res;
}
long long get_range(int l, int r) const {
if (r < l) return 0LL;
l ++; r ++;
return get(r) - get(l - 1);
}
void modify(int i, int v) {
for (i ++; i <= n; i += i & -i) bit[i] += v;
}
};
const char base[] = {'A', 'G', 'C', 'U'};
struct Trie {
const static int M = 2e6 + 7;
int node[M][4];
int num_node;
int ind[26];
int cnt[M];
int tin[M];
int tout[M];
Trie() {
num_node = 0;
for (int i = 0; i < 4; i ++) {
ind[base[i] - 'A'] = i;
}
}
int add(string &s) {
int cur = 0;
for (int i = 0; i < (int) s.size(); i ++) {
int c = ind[s[i] - 'A'];
if (node[cur][c] == 0) {
node[cur][c] = ++ num_node;
}
cur = node[cur][c];
}
cnt[cur] ++;
return cur;
}
int find_str(string &s) {
int cur = 0;
for (int i = 0; i < (int) s.size(); i ++) {
int c = ind[s[i] - 'A'];
if (node[cur][c] == 0) {
return - 1;
}
cur = node[cur][c];
}
return cur;
}
int timer = 0;
void dfs_pre(int u = 0) {
tin[u] = timer ++;
for (int i = 0; i < 4; i ++) if (node[u][i]) {
dfs_pre(node[u][i]);
}
tout[u] = timer - 1;
}
} pref, suff;
const int N = 2e6 + 7;
int pos[N];
long long rem[N];
long long res[N];
vector<pair<int, int>> qr[N];
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i ++) {
string s; cin >> s;
int u = pref.add(s);
reverse(s.begin(), s.end());
int v = suff.add(s);
pos[u] = v;
}
pref.dfs_pre();
suff.dfs_pre();
for (int i = 1; i <= m; i ++) {
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
int u = pref.find_str(p);
int v = suff.find_str(q);
if (u < 0 || v < 0) {
continue;
}
qr[u].emplace_back(v, i);
}
fenwick_tree f(pref.num_node);
function<void(int)> dfs = [&](int u) {
for (auto [v, i]: qr[u]) {
rem[i] = f.get_range(suff.tin[v], suff.tout[v]);
}
if (pref.cnt[u]) {
f.modify(suff.tin[pos[u]], pref.cnt[u]);
}
for (int i = 0; i < 4; i ++) if (pref.node[u][i]) {
dfs(pref.node[u][i]);
}
for (auto [v, i]: qr[u]) {
res[i] = f.get_range(suff.tin[v], suff.tout[v]);
}
};
dfs(0);
for (int i = 1; i <= m; i ++) {
cout << res[i] - rem[i] << '\n';
}
return 0;
}
Compilation message
selling_rna.cpp: In lambda function:
selling_rna.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | for (auto [v, i]: qr[u]) {
| ^
selling_rna.cpp:129:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
129 | for (auto [v, i]: qr[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
47316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
98784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
48852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
47316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
