#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 450;
const ll inf = 1e15;
const ll mod = 1e9+7;
const ll mod1 = 1e9+3;
const int base = 311;
const int base1 = 97;
int n, k, m, lab[N], a[N], b[N], c[N], d[N], t, cnt;
ll ans, tong;
string s[N];
struct node
{
int x[4];
vector<int> val;
node(){}
node(int t)
{
memset(x, t, sizeof(x));
}
};
char ch[4] = {'A', 'U', 'G', 'C'};
vector<node> q;
void add(int id)
{
int i = 0;
for(int j = 0; j < (int)s[id].length(); j ++)
{
int k = 0;
for(int p = 0; p < 4; p ++)
{
if(ch[p] == s[id][j])
{
k = p;
break;
}
}
if(q[i].x[k] == 0)
{
q[i].x[k] = q.size();
q.pb(node(0));
}
i = q[i].x[k];
q[i].val.pb(id);
}
}
int get(string s, int l, int r)
{
if(l > r)return 0;
int i = 0;
for(int j = 0; j < (int)s.length(); j ++)
{
int k = 0;
for(int p = 0; p < 4; p ++)
{
if(ch[p] == s[j])
{
k = p;
break;
}
}
if(q[i].x[k] == 0)return 0;
i = q[i].x[k];
}
return upper_bound(q[i].val.begin(), q[i].val.end(), r) - lower_bound(q[i].val.begin(), q[i].val.end(), l);
}
struct IT
{
int n;
vector<int> st, lazy;
IT(int _n)
{
n = _n;
st.resize(n*4+4, 0);
lazy.resize(n*4+4, 0);
}
void down(int id, int l, int r, int mid)
{
if(lazy[id] == 0)return;
st[id<<1] = (mid-l+1) - st[id<<1];
st[id<<1|1] = (r-mid) - st[id<<1|1];
lazy[id<<1] ^= lazy[id];
lazy[id<<1|1] ^= lazy[id];
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v)
{
if(u <= l && r <= v)
{
st[id] = (r-l+1) - st[id];
lazy[id] ^= 1;
}
if(u > r || l > v)return;
int mid = (l+r)>>1;
down(id, l, r, mid);
update(id<<1, l, mid, u, v);
update(id<<1|1, mid+1, r, u, v);
st[id] = st[id<<1]+st[id<<1|1];
}
void update(int l, int r)
{
update(1, 1, n, l, r);
}
int get(int id, int l, int r, int u, int v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v)return 0;
int mid = (l+r)>>1;
down(id, l, r, mid);
return get(id<<1, l, mid, u, v) + get(id<<1|1, mid+1, r, u, v);
}
int get(int l, int r)
{
return get(1, 1, n, l ,r);
}
};
vector<int> vi;
bool strmin(string x, string y)
{
for(int i = 0; i < (int)min(x.length(), y.length()); i ++)
{
if(x[i] < y[i])return true;
if(x[i] > y[i])return false;
}
if(x.length() >= y.length())return false;
return true;
}
bool strmax(string x, string y)
{
for(int i = 0; i < (int)min(x.length(), y.length()); i ++)
{
if(x[i] > y[i])return true;
if(x[i] < y[i])return false;
}
if(x.length() >= y.length())return false;
return true;
}
void sol()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> s[i];
sort(s+1, s+1+n);
q.pb(node(0));
for(int i = 1; i <= n; i ++)
{
//cout << s[i] << '\n';
reverse(s[i].begin(), s[i].end());
add(i);
reverse(s[i].begin(), s[i].end());
}
while(m -- > 0)
{
string pre, suf;
cin >> pre >> suf;
reverse(suf.begin(), suf.end());
int l = 1, r = n, mid;
while(l <= r)
{
mid = (l+r)>>1;
if(strmax(s[mid], pre))r = mid-1;
else l = mid+1;
}
k = r;
l = 1;
while(l <= r)
{
mid = (l+r)>>1;
if(strmin(s[mid], pre))l = mid+1;
else r = mid-1;
}
r = k;
//cout << l <<" "<<r<<'\n';
cout << get(suf, l, r) << '\n';
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
/*
*/
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:194:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:195:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
147348 KB |
Output is correct |
| 2 |
Correct |
246 ms |
143616 KB |
Output is correct |
| 3 |
Incorrect |
82 ms |
24072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
7580 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
7608 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
