| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 521564 | tengiz05 | Selling RNA Strands (JOI16_selling_rna) | C++17 | 0 ms | 0 KiB |
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 i64 = long long;
constexpr i64 P = 1E9 + 7, M = 7;
struct Node {
Node *to[4];
int mn, mx;
Node() {
mn = 1E9, mx = 0;
to[0] = to[1] = to[2] = to[3] = nullptr;
}
};
void add(Node *u, std::string &s, int i, int p) {
if (i == int(s.size())) {
u->mn = std::min(u->mn, p);
u->mx = std::max(u->mx, p);
return;
}
int x = std::string("AGCU").find(s[i]);
if (u->to[x] == nullptr) {
u->to[x] = new Node();
}
add(u->to[x], s, i + 1, p);
u->mn = std::min(u->mn, p);
u->mx = std::max(u->mx, p);
}
std::pair<int, int> find(Node *u, std::string &s, int i) {
if (i == int(s.size())) {
return {u->mn, u->mx};
}
int x = std::string("AGCU").find(s[i]);
if (u->to[x] == nullptr) {
return {-1, -1};
}
return find(u->to[x], s, i + 1);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::string> s(n);
Node *root = new Node();
for (int i = 0; i < n; i++) {
std::cin >> s[i];
}
std::sort(s.begin(), s.end());
for (int i = 0; i < n; i++) {
add(root, s[i], 0, i);
}
std::vector<std::tuple<int, int, int, int>> Q;
std::vector<int> f;
for (int i = 0; i < m; i++) {
std::string p, q;
std::cin >> p >> q;
auto [l, r] = find(root, p, 0);
if (l == -1) {
continue;
}
r++;
i64 H = 0;
for (char c : q) {
H *= M;
H += std::string("AGCU").find(c) + 1;
H %= P;
}
Q.emplace_back(l, H, i, -1);
Q.emplace_back(r, H, i, 1);
f.push_back(H);
}
for (int i = 0; i < n; i++) {
i64 h = 0, pw = 1;
for (int j = int(s[i].size()) - 1; j >= 0; j--) {
h = (h + pw * (std::string("AGCU").find(s[i][j]) + 1)) % P;
pw *= M;
pw %= P;
f.push_back(h);
}
}
std::sort(f.begin(), f.end());
f.erase(std::unique(f.begin(), f.end()), f.end());
std::sort(Q.begin(), Q.end());
std::vector<int> ans(m);
// std::vector<int> cnt(f.size());
// std::map<int, int> cnt;
int j = 0;
for (int i = 0; i < n; i++) {
int p, H, id, t;
while (j < int(Q.size())) {
std::tie(p, H, id, t) = Q[j];
if (p != i) {
break;
}
assert(std::binary_search(f.begin(), f.end(), H));
// H = std::lower_bound(f.begin(), f.end(), H) - f.begin();
ans[id] += t * cnt[H];
j++;
}
i64 h = 0, pw = 1;
for (int j = int(s[i].size()) - 1; j >= 0; j--) {
h = (h + pw * (std::string("AGCU").find(s[i][j]) + 1)) % P;
pw *= M;
pw %= P;
assert(std::binary_search(f.begin(), f.end(), h));
// h = std::lower_bound(f.begin(), f.end(), h) - f.begin();
cnt[h]++;
}
}
while (j < int(Q.size())) {
int p, H, id, t;
std::tie(p, H, id, t) = Q[j];
assert(std::binary_search(f.begin(), f.end(), H));
// H = std::lower_bound(f.begin(), f.end(), H) - f.begin();
ans[id] += t * cnt[H];
j++;
}
for (int i = 0; i < m; i++) {
std::cout << ans[i] << "\n";
}
return 0;
}