#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))
using namespace std;
class segtree{
int n;
vector<int> tree;
int update(int s, int l, int r, int pos, int x){
if (l > pos || r < pos) return tree[s];
if (l == r) return tree[s] += x;
int m = (l + r)>>1;
int a = update(2*s, l, m, pos, x);
int b = update(2*s+1, m+1, r, pos, x);
return tree[s] = a+b;
}
int query(int s, int l, int r, int ql, int qr) const {
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return tree[s];
int m = (l + r)>>1;
int a = query(2*s, l, m, ql, qr);
int b = query(2*s+1, m+1, r, ql, qr);
return a+b;
}
public:
segtree(int n = 0){ Assign(n); }
void Assign(int s){
n = highpow(s);
if (bitcnt(s) > 1) n <<= 1;
tree.assign(2*n, 0);
}
void update(int pos, int x){ update(1, 0, n-1, pos, x); }
int query(int l, int r) const { return query(1, 0, n-1, l, r); }
void Print() const { for (int i = n; i < 2*n; i++) cout << tree[i] << sp; cout << en; }
};
struct Trie{
static map<char, int> mp;
int n;
vector<vector<int> > g;
vector<int> word, in, out;
Trie(int mx){
g.assign(mx, vector<int>(4, -1));
word.assign(mx, 0);
in.assign(mx, 0);
out.assign(mx, 0);
n = 1;
}
int Add(int s, string str, int i){
if (i == str.size()){
word[s]++;
return s;
}
int x = mp[str[i]];
if (!~g[s][x]) g[s][x] = n++;
return Add(g[s][x], str, i+1);
}
int Find(int s, string str, int i) const {
if (i == str.size()) return s;
int x = mp[str[i]];
if (!~g[s][x]) return -1;
return Find(g[s][x], str, i+1);
}
int Compute(int s = 0, int t = 0){
in[s] = t;
for (int u : g[s])
if (~u)
t = Compute(u, t+1);
return out[s] = t;
}
void Print() const {
for (int i = 0; i < n; i++)
for (int j = 0; j < 4; j++)
if (~g[i][j])
cout << i << sp << g[i][j] << sp << j << en;
cout << en;
for (int i = 0; i < n; i++)
cout << word[i] << sp << in[i] << sp << out[i] << en;
cout << en;
}
};
map<char, int> Trie::mp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
const ll LINF = 4e18;
const int mxN = 2e6+10, INF = 2e9;
ll n, m, ans[mxN], mp[mxN];
vector<array<int, 2> > q[mxN];
Trie pre(mxN), suf(mxN);
segtree st;
void dfs(int s){
for (auto [u, i] : q[s])
ans[i] = st.query(suf.in[u], suf.out[u]);
if (pre.word[s]) st.update(suf.in[mp[s]], pre.word[s]);
for (int u : pre.g[s])
if (~u)
dfs(u);
for (auto [u, i] : q[s])
ans[i] = st.query(suf.in[u], suf.out[u]) - ans[i];
}
void Solve(){
cin >> n >> m;
for (int i = 0; i < n; i++){
rs(s);
int u = pre.Add(0, s, 0);
reverse(all(s));
int v = suf.Add(0, s, 0);
mp[u] = v;
}
pre.Compute();
suf.Compute();
st.Assign(suf.n);
for (int i = 0; i < m; i++){
rs(s); rs(t);
reverse(all(t));
int u = pre.Find(0, s, 0);
int v = suf.Find(0, t, 0);
if (~u && ~v) q[u].pb({v, i});
}
dfs(0);
for (int i = 0; i < m; i++)
cout << ans[i] << en;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cerr.tie(0);
cout << setprecision(12) << fixed;
cerr << setprecision(12) << fixed;
cerr << "Started!" << endl;
int t = 1;
//cin >> t;
while (t--)
Solve();
return 0;
}
Compilation message
selling_rna.cpp: In member function 'int Trie::Add(int, std::string, int)':
selling_rna.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (i == str.size()){
| ~~^~~~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::Find(int, std::string, int) const':
selling_rna.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if (i == str.size()) return s;
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
313420 KB |
Output is correct |
| 2 |
Correct |
243 ms |
313440 KB |
Output is correct |
| 3 |
Correct |
258 ms |
313420 KB |
Output is correct |
| 4 |
Correct |
246 ms |
313368 KB |
Output is correct |
| 5 |
Correct |
257 ms |
313384 KB |
Output is correct |
| 6 |
Correct |
249 ms |
313484 KB |
Output is correct |
| 7 |
Correct |
264 ms |
313420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1607 ms |
338148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
337 ms |
314700 KB |
Output is correct |
| 2 |
Correct |
311 ms |
314316 KB |
Output is correct |
| 3 |
Correct |
349 ms |
314500 KB |
Output is correct |
| 4 |
Correct |
310 ms |
314180 KB |
Output is correct |
| 5 |
Correct |
309 ms |
314188 KB |
Output is correct |
| 6 |
Correct |
317 ms |
314428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
313420 KB |
Output is correct |
| 2 |
Correct |
243 ms |
313440 KB |
Output is correct |
| 3 |
Correct |
258 ms |
313420 KB |
Output is correct |
| 4 |
Correct |
246 ms |
313368 KB |
Output is correct |
| 5 |
Correct |
257 ms |
313384 KB |
Output is correct |
| 6 |
Correct |
249 ms |
313484 KB |
Output is correct |
| 7 |
Correct |
264 ms |
313420 KB |
Output is correct |
| 8 |
Execution timed out |
1607 ms |
338148 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
