#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;
map<char, int> _mp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
const ll LINF = 4e18;
const int mxN = 2e6+10, INF = 2e9;
ll n, m, N[2], word[mxN], in[mxN], out[mxN], ans[mxN], mp[mxN], g[2][mxN][4], tree[mxN];
vector<array<int, 2> > q[mxN];
ll query(int pos){
if (pos > N[1]) pos = N[1];
ll sum = 0;
for (; pos; pos -= (pos & (-pos)))
sum += tree[pos];
return sum;
}
ll query(int l, int r){
l++; r++;
if (l > r) return 0;
return query(r) - query(l-1);
}
void update(int pos, ll x){
pos++;
if (pos <= 0) return;
for (; pos <= N[1]; pos += (pos & (-pos)))
tree[pos] += x;
}
template<int t>
int Add(int s, string str, int i){
if (i == str.size()){
if (!t) word[s]++;
return s;
}
int x = _mp[str[i]];
if (!~g[t][s][x]) g[t][s][x] = N[t]++;
return Add<t>(g[t][s][x], str, i+1);
}
template<int t>
int Find(int s, string str, int i){
if (i == str.size()) return s;
int x = _mp[str[i]];
if (!~g[t][s][x]) return -1;
return Find<t>(g[t][s][x], str, i+1);
}
int Compute(int s = 0, int t = 0){
in[s] = t;
for (int u : g[1][s])
if (~u)
t = Compute(u, t+1);
return out[s] = t;
}
void dfs(int s){
for (auto [u, i] : q[s])
ans[i] = query(in[u], out[u]);
if (word[s]) update(in[mp[s]], word[s]);
for (int u : g[0][s])
if (~u) dfs(u);
for (auto [u, i] : q[s])
ans[i] = query(in[u], out[u]) - ans[i];
}
void Solve(){
memset(g, -1, sizeof(g));
N[0] = N[1] = 1;
cin >> n >> m;
for (int i = 0; i < n; i++){
rs(s);
int u = Add<0>(0, s, 0);
reverse(all(s));
int v = Add<1>(0, s, 0);
mp[u] = v;
}
Compute();
cout << 1 << endl;
for (int i = 0; i < m; i++){
rs(s); rs(t);
reverse(all(t));
int u = Find<0>(0, s, 0);
int v = Find<1>(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 instantiation of 'int Add(int, std::string, int) [with int t = 0; std::string = std::__cxx11::basic_string<char>]':
selling_rna.cpp:104:31: required from here
selling_rna.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if (i == str.size()){
| ~~^~~~~~~~~~~~~
selling_rna.cpp: In instantiation of 'int Add(int, std::string, int) [with int t = 1; std::string = std::__cxx11::basic_string<char>]':
selling_rna.cpp:106:31: required from here
selling_rna.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
selling_rna.cpp: In instantiation of 'int Find(int, std::string, int) [with int t = 0; std::string = std::__cxx11::basic_string<char>]':
selling_rna.cpp:114:32: required from here
selling_rna.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if (i == str.size()) return s;
| ~~^~~~~~~~~~~~~
selling_rna.cpp: In instantiation of 'int Find(int, std::string, int) [with int t = 1; std::string = std::__cxx11::basic_string<char>]':
selling_rna.cpp:115:32: required from here
selling_rna.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
172492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1595 ms |
197212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
173792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
172492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
