Submission #112366

#TimeUsernameProblemLanguageResultExecution timeMemory
112366MAMBASelling RNA Strands (JOI16_selling_rna)C++17
35 / 100
584 ms346064 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i , j , k) for (int i = j; i < (int)k; i++) #define pb push_back #define mt make_tuple #define all(x) x.begin(),x.end() typedef long long ll; typedef pair<int , int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef long double ld; typedef complex<ld> point; inline void fileIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } template<class T , class S> inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; } template<class T , class S> inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; } constexpr int N = 2e6 + 10; constexpr int MOD = 1e9 + 7; template<typename T> inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; } template<typename S, typename T> inline S add(S &l, T r) { return mod(l += r); } map<char , int> mp({{'A' , 0} , {'G' , 1} , {'C' , 2} , {'U' , 3}}); int n , m, cnt[2]; string s[N], h[N], q[N]; int nxt[2][N][4]; vector<pii> vec[N]; int st[N], en[N], tme; void dfs1(int v) { st[v] = tme++; rep(i , 0 , 4) if (nxt[0][v][i]) dfs1(nxt[0][v][i]); en[v] = tme; } int sz[N], pos[N], res[N]; vi have[N]; int seg[N << 1]; inline void segClear(int v = 1) { if (!seg[v]) return; seg[v] = 0; if ((v << 1) < N) segClear(v << 1); if ((v << 1 | 1) < N) segClear(v << 1 | 1); } inline void segAdd(int pos) { for (pos += cnt[0] + 1; pos; pos >>= 1) seg[pos]++; } inline int segGet(int l , int r) { int res = 0; for (l += cnt[0] + 1, r += cnt[0] + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res += seg[l++]; if (r & 1) res += seg[--r]; } return res; } void dfsAdd(int v) { for (auto e : have[v]) segAdd(st[pos[e]]); rep(i , 0 ,4) { int u = nxt[1][v][i]; if (u) dfsAdd(u); } } void dfs2(int v) { int mx = -1, id =-1; rep(i , 0 , 4) if (nxt[1][v][i] && smax(mx , sz[nxt[1][v][i]])) id = i; rep(i , 0 , 4) { int u = nxt[1][v][i]; if (u && i != id) { dfs2(u); segClear(); } } if (~id) dfs2(nxt[1][v][id]); rep(i , 0 , 4) { int u = nxt[1][v][i]; if (u && i != id) dfsAdd(u); } for (auto e : have[v]) segAdd(st[pos[e]]); for (auto e : vec[v]) res[e.second] = segGet(st[e.first] , en[e.first]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef LOCAL // fileIO("forbidden1"); #endif cin >> n >> m; rep(i , 0 , n) { cin >> s[i]; auto f = [i](int id) -> int { int now = 0; if (id == 1) sz[0]++; for (auto e : s[i]) { if (!nxt[id][now][mp[e]]) nxt[id][now][mp[e]] = ++cnt[id]; now = nxt[id][now][mp[e]]; if (id == 1) sz[now]++; } return now; }; pos[i] = f(0); reverse(all(s[i])); have[f(1)].pb(i); } rep(i , 0 , m) { cin >> h[i] >> q[i]; reverse(all(q[i])); auto f = [](int id, string &st) -> int { int now = 0; for (auto e : st) { if (!nxt[id][now][mp[e]]) return -1; now = nxt[id][now][mp[e]]; } return now; }; int lid = f(0, h[i]); int rid = f(1 ,q[i]); if (!~min(lid , rid)) continue; vec[rid].pb({lid , i}); } dfs1(0); dfs2(0); rep(i , 0 , m) cout << res[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...