#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 520;
const ll base = 35711;
struct Trie{
struct node{
ll c[10];
ll l, r;
vector<ll>range;
}; node x[N];
ll cur;
Trie() : cur(0){
memset(x[0].c, -1, sizeof(x[0]));
x[0].l = inf;
x[0].r = -inf;
}
ll init(){
cur++;
memset(x[cur].c, -1, sizeof(x[cur]));
x[cur].l = inf, x[0].r = -inf;
return cur;
}
void add(string s, ll idx){
ll pos = 0;
for(auto f : s){
ll c = f - 'A';
if(x[pos].c[c] == -1) x[pos].c[c] = init();
pos = x[pos].c[c];
x[pos].range.pb(idx);
x[pos].l = min(idx, x[pos].l);
x[pos].r = max(idx, x[pos].r);
}
}
pll find_range(string s){
ll pos = 0;
for(auto f : s){
ll c = f - 'A';
pos = x[pos].c[c];
}
return {x[pos].l, x[pos].r};
}
vector<ll>dfs(string s){
ll pos = 0;
vector<ll>tmp;
for(auto f : s){
ll c = f - 'A';
pos = x[pos].c[c];
if(pos == -1) return tmp;
}
return x[pos].range;
}
};
string cnv(string s){
string ans = s;
for(int i = 0; i < ans.size();i++){
if(ans[i] == 'C') ans[i] = 'B';
else if(ans[i] == 'G') ans[i] = 'C';
else if(ans[i] == 'U') ans[i] = 'D';
}
return ans;
}
Trie rev, tr;
void to_nho_cau(){
ll n,m; cin >> n >> m;
vector<string>v;
for(int i = 1; i <= n;i++){
string s; cin >> s;
s = cnv(s);
v.pb(s);
}
sort(all(v));
for(int i = 0; i < v.size();i++){
tr.add(v[i], i);
string t = v[i]; reverse(all(t));
rev.add(t, i);
}
while(m--){
string p,q; cin >> p >> q;
p = cnv(p), q = cnv(q);
reverse(all(q));
pll cur = tr.find_range(p);
ll l = cur.F, r = cur.S;
vector<ll>res = rev.dfs(q);
if(!res.size() || l > r){
cout << 0 << '\n';
continue;
}
ll high = upper_bound(all(res), r) - res.begin();
ll low = lower_bound(all(res), l) - res.begin();
cout << high - low << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) to_nho_cau();
}
Compilation message
selling_rna.cpp: In function 'std::string cnv(std::string)':
selling_rna.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < ans.size();i++){
| ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void to_nho_cau()':
selling_rna.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < v.size();i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
95824 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
100236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
99060 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
95824 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
