#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 (i ++, 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;
return get(r) - get(l - 1);
}
void modify(int i, int v) {
i ++;
if (i == 0) {
return;
}
for (; 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() {
memset(node, 0, sizeof node);
memset(tin, 0, sizeof tin);
memset(tout, 0, sizeof tout);
memset(cnt, 0, sizeof cnt);
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;
}
void dfs_pre(int u = 0) {
static int timer = 0;
tin[u] = ++ timer;
for (int i = 0; i < 4; i ++) if (node[u][i]) {
dfs_pre(node[u][i]);
}
tout[u] = timer;
}
} 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 + 7);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
156860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
157372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
158412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
156860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
