Submission #1230169

#TimeUsernameProblemLanguageResultExecution timeMemory
1230169hiderrSelling RNA Strands (JOI16_selling_rna)C++20
100 / 100
255 ms231248 KiB
#include <bits/stdc++.h> using namespace std; #define loop(i, a, b) for(int i = a; i <= b; i++) #define loop_rev(i, a, b) for(int i = a; i >= b; i--) #define all(x) x.begin(), x.end() #define sz(x) int(x.size()) #define pb push_back using ll = long long; struct TreeNode { int l = 0, r = 0, sum = 0; }; const int TREE_BASE = (1 << 18); TreeNode st_pool[(1 << 18) * 18 + 1'000]; int st_node() { static int node_id = 0; return ++node_id; } struct SegTree { int root = 0; void update(int i, int val, int& v, int l, int r) { if(v == 0) v = st_node(); st_pool[v].sum += val; if(l != r) { int mid = (l + r) / 2; if(i <= mid) update(i, val, st_pool[v].l, l, mid); else update(i, val, st_pool[v].r, mid + 1, r); } } void update(int i, int val) { update(i, val, root, 0, TREE_BASE - 1); } int query(int a, int b, int v, int l, int r) { if(v == 0) return 0; if(l >= a && r <= b) { return st_pool[v].sum; } int mid = (l + r) / 2, res = 0; if(a <= mid) { res += query(a, b, st_pool[v].l, l, mid); // BUG FOUND: Quadratic query (l <= mid instead of a <= mid) } if(b > mid) { res += query(a, b, st_pool[v].r, mid + 1, r); } return res; } int query(int a, int b) { return query(a, b, root, 0, TREE_BASE - 1); } void include(int &v_this, int v_other) { if(v_other == 0) return; if(v_this == 0) { v_this = v_other; return; } if(st_pool[v_other].l) include(st_pool[v_this].l, st_pool[v_other].l); if(st_pool[v_other].r) include(st_pool[v_this].r, st_pool[v_other].r); st_pool[v_this].sum = st_pool[st_pool[v_this].l].sum + st_pool[st_pool[v_this].r].sum; } void include_disjoint_segtree(SegTree& other) { include(root, other.root); } }; struct TrieNode { int ptr[4]; vector<int> values; int tin = 0, tout = 0; SegTree st; }; const int MAX_LEN = 2'000'000; TrieNode trie_pool[2 * MAX_LEN + 1'000]; int trie_node() { static int node_id = 0; return ++node_id; } struct Trie { int root = trie_node(); int insert(string const& s, int value) { int v = root; loop(i, 0, sz(s) - 1) { int& dest = trie_pool[v].ptr[s[i] - 'a']; if(!dest) dest = trie_node(); v = dest; } trie_pool[v].values.pb(value); return v; } int find(string const& s) { int v = root; loop(i, 0, sz(s) - 1) { if(!v) return 0; int& dest = trie_pool[v].ptr[s[i] - 'a']; v = dest; } return v; } void euler_tour() { int timer = 1; _euler_tour(root, timer); } void _euler_tour(int v, int& timer) { int cnt = 0; for(int s : trie_pool[v].ptr) cnt += (s != 0); trie_pool[v].tin = timer; for(int s : trie_pool[v].ptr) { if(!s) continue; if(sz(trie_pool[v].values) || cnt > 1) ++timer; _euler_tour(s, timer); } trie_pool[v].tout = timer; } vector<int> rev_topo() { vector<int> res; _rev_topo(root, res); return res; } void _rev_topo(int v, vector<int>& res) { for(int s : trie_pool[v].ptr) { if(s) _rev_topo(s, res); } res.pb(v); } }; void F(string& s) { for(char& c : s) if(c == 'A') c = 'a'; else if(c == 'G') c = 'b'; else if(c == 'C') c = 'c'; else if(c == 'U') c = 'd'; } int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector<int> trie_id(n + 1); vector<string> S(n + 1); Trie pref, suff; loop(i, 1, n) { cin >> S[i]; F(S[i]); trie_id[i] = pref.insert(S[i], i); } pref.euler_tour(); loop(i, 1, n) { reverse(all(S[i])); suff.insert(S[i], i); } vector<int> res(m + 1); vector<int> id_p(m + 1); auto order = suff.rev_topo(); loop(i, 1, m) { string p, q; cin >> p >> q; F(p), F(q); id_p[i] = pref.find(p); reverse(all(q)); int id_q = suff.find(q); if(id_q != 0) { trie_pool[id_q].values.pb(-i); } } for(int v : order) { for(int s : trie_pool[v].ptr) { if(s) trie_pool[v].st.include_disjoint_segtree(trie_pool[s].st); } for(int val : trie_pool[v].values) { if(val > 0) { trie_pool[v].st.update(trie_pool[trie_id[val]].tin, 1); } else { int q_ind = (-val), pref_id = id_p[q_ind]; if(pref_id != 0) res[q_ind] = trie_pool[v].st.query(trie_pool[pref_id].tin, trie_pool[pref_id].tout); } } } loop(i, 1, m) { cout << res[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...