제출 #1070411

#제출 시각아이디문제언어결과실행 시간메모리
1070411windowwifeSelling RNA Strands (JOI16_selling_rna)C++17
60 / 100
1608 ms557808 KiB
#include<bits/stdc++.h> #define ll long long #define task "" using namespace std; const int maxn = 3e6 + 2, mod = 998244353; int n, res, numnode, m; string s[maxn], p, q; vector<int> ok; struct Node { int child[26]; int l, r; vector<int> v; }node[maxn]; struct PrefixTrie { void add (int idx, string &s) { int cur = 0; for (char c : s) { if (node[cur].child[c - 'A'] == 0) { cur = node[cur].child[c - 'A'] = ++numnode; node[cur].l = node[cur].r = idx; } else { cur = node[cur].child[c - 'A']; node[cur].r = idx; } } } pair<int, int> find (string &s) { int cur = 0; for (char c : s) { if (node[cur].child[c - 'A'] == 0) return {0, 0}; cur = node[cur].child[c - 'A']; } return {node[cur].l, node[cur].r}; } }ptrie; struct SuffixTrie { void add (int idx, string &s) { int cur = 0; for (char c : s) { if (node[cur].child[c - 'A'] == 0) cur = node[cur].child[c - 'A'] = ++numnode; else cur = node[cur].child[c - 'A']; node[cur].v.push_back(idx); } } vector<int> find (string &s) { int cur = 0; for (char c : s) { if (node[cur].child[c - 'A'] == 0) return {}; cur = node[cur].child[c - 'A']; } return node[cur].v; } }strie; int main() { //freopen(task".INP", "r", stdin); //freopen(task".OUT", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> s[i]; sort(s + 1, s + n + 1); for (int i = 1; i <= n; i++) ptrie.add(i, s[i]); for (int i = 1; i <= n; i++) { reverse(s[i].begin(), s[i].end()); strie.add(i, s[i]); } while (m--) { cin >> p >> q; reverse(q.begin(), q.end()); auto [L, R] = ptrie.find(p); ok = strie.find(q); if (L == 0 || ok.empty()) { cout << 0 << '\n'; continue; } ok.push_back(n + 1); cout << upper_bound(ok.begin(), ok.end(), R) - lower_bound(ok.begin(), ok.end(), L) << '\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...