# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
972576 | 2024-04-30T16:23:41 Z | duckindog | Selling RNA Strands (JOI16_selling_rna) | C++17 | 1429 ms | 1048576 KB |
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10, base = 19973; int n, m; string str[N]; string st[N], ed[N]; int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; } int nwt[N << 2][4]; bool mk[N << 2]; struct Trie { int it; vector<array<int, 4>> nwt; vector<int> sz; Trie() : nwt(1), sz(1) {} void add(string s) { int g = 0; for (int i = 1; i <= (int)s.size(); ++i) { while (nwt.size() <= g) nwt.push_back(array<int, 4>()); int path = convert(s[i - 1]); if (!nwt[g][path]) nwt[g][path] = ++it; g = nwt[g][path]; while (sz.size() <= it) sz.push_back(0); sz[g] += 1; } } int get(string s) { int g = 0; for (int i = 1; i <= (int)s.size(); ++i) { int path = convert(s[i - 1]); if (!nwt[g][path]) return 0; g = nwt[g][path]; } return sz[g]; } } T[N << 2]; int it; void mark(string s) { int g = 0; for (int i = 1; i <= (int)s.size(); ++i) { int path = convert(s[i - 1]); if (!nwt[g][path]) nwt[g][path] = ++it; g = nwt[g][path]; } mk[g] = true; } void add(string s) { string rs = string(s.rbegin(), s.rend()); int g = 0; for (int i = 1; i <= (int)s.size(); ++i) { int path = convert(s[i - 1]); if (!nwt[g][path]) nwt[g][path] = ++it; g = nwt[g][path]; if (mk[g]) T[g].add(rs); } } int get(string s, const auto& e) { int g = 0; for (int i = 1; i <= (int)s.size(); ++i) { int path = convert(s[i - 1]); g = nwt[g][path]; } return T[g].get(string(e.rbegin(), e.rend())); } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> str[i]; for (int i = 1; i <= m; ++i) cin >> st[i] >> ed[i]; for (int i = 1; i <= m; ++i) mark(st[i]); for (int i = 1; i <= n; ++i) add(str[i]); for (int i = 1; i <= m; ++i) cout << get(st[i], ed[i]) << "\n"; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 59220 KB | Output is correct |
2 | Correct | 32 ms | 59228 KB | Output is correct |
3 | Correct | 33 ms | 59228 KB | Output is correct |
4 | Correct | 31 ms | 59188 KB | Output is correct |
5 | Correct | 32 ms | 59220 KB | Output is correct |
6 | Correct | 33 ms | 59224 KB | Output is correct |
7 | Correct | 32 ms | 59220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1429 ms | 1048576 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 50 ms | 59984 KB | Output is correct |
2 | Correct | 54 ms | 60756 KB | Output is correct |
3 | Correct | 54 ms | 60244 KB | Output is correct |
4 | Correct | 43 ms | 59752 KB | Output is correct |
5 | Correct | 52 ms | 59960 KB | Output is correct |
6 | Correct | 53 ms | 60040 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 59220 KB | Output is correct |
2 | Correct | 32 ms | 59228 KB | Output is correct |
3 | Correct | 33 ms | 59228 KB | Output is correct |
4 | Correct | 31 ms | 59188 KB | Output is correct |
5 | Correct | 32 ms | 59220 KB | Output is correct |
6 | Correct | 33 ms | 59224 KB | Output is correct |
7 | Correct | 32 ms | 59220 KB | Output is correct |
8 | Runtime error | 1429 ms | 1048576 KB | Execution killed with signal 9 |
9 | Halted | 0 ms | 0 KB | - |