#include <bits/stdc++.h>
using namespace std;
// clang-format off
template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable< T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) { cout << "["; for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", "; } return cout << "]";}
#ifdef LOCAL
void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
// clang-format on
using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
constexpr int A = 4;
struct node {
int tin, tout;
array<int, 4> c;
node() : tin(0), tout(0), c({-1, -1, -1, -1}) {}
};
template <typename T> struct fen {
vector<T> tr;
ll mxn;
fen(ll sz) {
mxn = sz;
tr.assign(sz + 5, 0);
}
void upd(ll g, T k) {
g++;
assert(g != 0);
for (; g <= mxn; g += g & -g)
tr[g] += k;
}
T ge(ll g) {
g++;
T res = 0;
for (; g; g -= g & -g)
res += tr[g];
return res;
}
T rng(ll l, ll r) { return ge(r) - ge(l - 1); }
};
constexpr int N = 2e6 + 5;
node p1[N], p2[N];
void solve() {
// open
int n, m;
cin >> n >> m;
vector<vector<int>> a(n);
for (auto &u : a) {
string s;
cin >> s;
u.resize(s.size());
for (int i = 0; i < (int)s.size(); i++) {
switch (s[i]) {
case 'A':
u[i] = 0;
break;
case 'C':
u[i] = 1;
break;
case 'G':
u[i] = 2;
break;
case 'U':
u[i] = 3;
break;
};
}
}
vector<vector<int>> fo(m), ba(m);
for (int i = 0; i < m; i++) {
string s;
cin >> s;
{
auto &u = fo[i];
u.resize(s.size());
for (int i = 0; i < (int)s.size(); i++) {
switch (s[i]) {
case 'A':
u[i] = 0;
break;
case 'C':
u[i] = 1;
break;
case 'G':
u[i] = 2;
break;
case 'U':
u[i] = 3;
break;
};
}
}
cin >> s;
{
auto &u = ba[i];
u.resize(s.size());
for (int i = 0; i < (int)s.size(); i++) {
switch (s[i]) {
case 'A':
u[i] = 0;
break;
case 'C':
u[i] = 1;
break;
case 'G':
u[i] = 2;
break;
case 'U':
u[i] = 3;
break;
};
}
reverse(all(u));
}
}
int pool_1_nxt = 1, pool_2_nxt = 1;
for (int i = 0; i < n; i++) {
debug(i);
const auto &h = a[i];
int cur = 0;
for (const auto u : h) {
if (p1[cur].c[u] == -1) {
p1[cur].c[u] = pool_1_nxt++;
}
cur = p1[cur].c[u];
}
auto hc = h;
reverse(all(hc));
cur = 0;
for (const auto u : hc) {
if (p2[cur].c[u] == -1) {
p2[cur].c[u] = pool_2_nxt++;
}
cur = p2[cur].c[u];
}
}
int cc = 0;
auto dfs = [&](auto &dfs, int g, auto pool) -> void {
pool[g].tin = cc++;
for (int i = 0; i < 4; i++) {
if (pool[g].c[i] != -1) {
dfs(dfs, pool[g].c[i], pool);
}
}
pool[g].tout = cc++;
};
dfs(dfs, 0, p1);
cc = 0;
dfs(dfs, 0, p2);
vector<array<int, 4>> range_query(m);
for (int i = 0; i < m; i++) {
auto &[l1, r1, l2, r2] = range_query[i];
int cur = 0;
for (auto u : fo[i]) {
if (p1[cur].c[u] == -1) {
l1 = r1 = -1;
break;
}
cur = p1[cur].c[u];
}
if (l1 != -1) {
l1 = p1[cur].tin;
r1 = p1[cur].tout;
}
cur = 0;
for (auto u : ba[i]) {
if (p2[cur].c[u] == -1) {
l2 = r2 = -1;
break;
}
cur = p2[cur].c[u];
}
if (r1 != -1) {
l2 = p2[cur].tin;
r2 = p2[cur].tout;
}
}
vector<pii> locations;
for (int i = 0; i < n; i++) {
int x = -1, y = -1;
const auto &h = a[i];
int cur = 0;
for (const auto u : h) {
cur = p1[cur].c[u];
}
x = cur;
auto hc = h;
cur = 0;
reverse(all(hc));
for (const auto u : hc) {
cur = p2[cur].c[u];
}
y = cur;
locations.pb({x, y});
}
int max_x = p1[0].tout + 1;
vector pt_bin(max_x, vector<int>());
vector add_bin(max_x, vector<array<int, 3>>());
vector sub_bin(max_x, vector<array<int, 3>>());
for (auto [x, y] : locations) {
pt_bin[x].pb(y);
}
for (int i = 0; i < m; i++) {
const auto [l1, r1, l2, r2] = range_query[i];
if (l1 != -1 and l2 != -1) {
if (l1 > 0) {
sub_bin[l1 - 1].pb({l2, r2, i});
}
add_bin[r1].pb({l2, r2, i});
}
}
int max_y = p2[0].tout + 1;
fen<ll> tree(max_y);
vector<ll> ans(m);
for (int x = 0; x < max_x; x++) {
for (auto y : pt_bin[x]) {
tree.upd(y, 1);
}
for (auto [l, r, qid] : sub_bin[x]) {
ans[qid] -= tree.rng(l, r);
}
for (auto [l, r, qid] : add_bin[x]) {
ans[qid] += tree.rng(l, r);
}
}
for (auto &u : ans)
cout << u << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(false);
ll T = 1;
// cin >> T;
for (int t = 0; t < T; t++)
solve();
cout.flush();
return 0;
}
Compilation message
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:11:22: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) "zzz"
| ^~~~~
selling_rna.cpp:141:5: note: in expansion of macro 'debug'
141 | debug(i);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
94300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
146516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
106948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
94300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
