#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
const int mxN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
map<char,ll> id;
struct Node{
Node* children[4];
vector<ll> points;
Node(){
for(ll i=0;i<4;++i) children[i]=NULL;
}
};
Node* p_root=new Node();
Node* s_root=new Node();
void add(Node* curr,string str,ll idx){
for(auto it:str){
if(curr->children[id[it]]==NULL) curr->children[id[it]]=new Node();
curr=curr->children[id[it]];
curr->points.pb(idx);
}
}
pair<ll,ll> qry(Node* curr,string str){
for(auto it:str){
if(curr->children[id[it]]==NULL) return {INF,-INF};
curr=curr->children[id[it]];
}
return {curr->points[0],curr->points[curr->points.size()-1]};
}
string rev(string str){
string ans;
for(ll i=str.size()-1;i>=0;--i){
ans.pb(str[i]);
}
return ans;
}
void solve() {
ll n,m;cin>>n>>m;
vector<string> full_str(n);
for(auto &it:full_str) cin>>it;
sort(all(full_str));
id['A']=0;
id['C']=1;
id['G']=2;
id['U']=3;
ll idx=1;
for(auto it:full_str){
add(p_root,it,idx);
add(s_root,rev(it),idx++);
}
for(ll i=0;i<m;++i){
string l,r;cin>>l>>r;
pair<ll,ll> p_range=qry(p_root,l);
if(p_range.first>p_range.second) cout<<0<<nl;
else{
bool f=0;
Node* curr=s_root;
for(auto it:rev(r)){
if(curr->children[id[it]]==NULL){
cout<<0<<nl;
f=1;
break;
}
curr=curr->children[id[it]];
}
if(!f){
ll l=lower_bound(all(curr->points),p_range.first)-curr->points.begin();
ll r=upper_bound(all(curr->points),p_range.second)-curr->points.begin();
cout<<r-l<<nl;
}
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
294 ms |
213508 KB |
Output is correct |
2 |
Correct |
279 ms |
201536 KB |
Output is correct |
3 |
Correct |
279 ms |
209740 KB |
Output is correct |
4 |
Correct |
290 ms |
200012 KB |
Output is correct |
5 |
Correct |
297 ms |
233192 KB |
Output is correct |
6 |
Correct |
321 ms |
236428 KB |
Output is correct |
7 |
Correct |
115 ms |
39660 KB |
Output is correct |
8 |
Correct |
262 ms |
168012 KB |
Output is correct |
9 |
Correct |
225 ms |
146260 KB |
Output is correct |
10 |
Correct |
191 ms |
140108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
4708 KB |
Output is correct |
2 |
Correct |
18 ms |
4048 KB |
Output is correct |
3 |
Correct |
25 ms |
4560 KB |
Output is correct |
4 |
Correct |
16 ms |
3828 KB |
Output is correct |
5 |
Correct |
18 ms |
4048 KB |
Output is correct |
6 |
Correct |
21 ms |
4356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
294 ms |
213508 KB |
Output is correct |
9 |
Correct |
279 ms |
201536 KB |
Output is correct |
10 |
Correct |
279 ms |
209740 KB |
Output is correct |
11 |
Correct |
290 ms |
200012 KB |
Output is correct |
12 |
Correct |
297 ms |
233192 KB |
Output is correct |
13 |
Correct |
321 ms |
236428 KB |
Output is correct |
14 |
Correct |
115 ms |
39660 KB |
Output is correct |
15 |
Correct |
262 ms |
168012 KB |
Output is correct |
16 |
Correct |
225 ms |
146260 KB |
Output is correct |
17 |
Correct |
191 ms |
140108 KB |
Output is correct |
18 |
Correct |
25 ms |
4708 KB |
Output is correct |
19 |
Correct |
18 ms |
4048 KB |
Output is correct |
20 |
Correct |
25 ms |
4560 KB |
Output is correct |
21 |
Correct |
16 ms |
3828 KB |
Output is correct |
22 |
Correct |
18 ms |
4048 KB |
Output is correct |
23 |
Correct |
21 ms |
4356 KB |
Output is correct |
24 |
Correct |
257 ms |
177748 KB |
Output is correct |
25 |
Correct |
298 ms |
177996 KB |
Output is correct |
26 |
Correct |
261 ms |
176160 KB |
Output is correct |
27 |
Correct |
247 ms |
175876 KB |
Output is correct |
28 |
Correct |
183 ms |
65564 KB |
Output is correct |
29 |
Correct |
80 ms |
25800 KB |
Output is correct |