//i_love_aisukiuwu
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/trucmai/.vim/tools.h"
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif
void open(){
if(fopen("i.inp","r")){
freopen("i.inp","r",stdin);
freopen("o.out","w",stdout);
}
}
#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "
const int MN1 = 1e5 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
struct trie{
struct node{
array<ll,26>nxt;
ll l,r; bool ex;
vector<ll>lst;
node(){}
node(ll l,ll r,bool ex):l(l),r(r),ex(ex){nxt.fill(-1);}
};
bool rev;
vector<node>tr{node(INF,-INF,false)};
trie(bool rev):rev(rev){}
void add(string &s,ll &idx){
ll ptr = 0;
for(ll i = 0;i < s.size();++i){
ll ch = s[i] - 'A';
if(tr[ptr].nxt[ch] == -1){
tr[ptr].nxt[ch] = tr.size();
tr.push_back(node(INF,-INF,false));
}
ptr = tr[ptr].nxt[ch];
if(!rev){
tr[ptr].l = min(tr[ptr].l,idx);
tr[ptr].r = max(tr[ptr].r,idx);
}else tr[ptr].lst.push_back(idx);
}
tr[ptr].ex = true;
}
pi get(string &s){
ll ptr = 0;
for(ll i = 0;i < s.size();++i){
ll ch = s[i] - 'A';
if(tr[ptr].nxt[ch] == -1) return {-1,-1};
ptr = tr[ptr].nxt[ch];
}
return {tr[ptr].l,tr[ptr].r};
}
ll query(string &s,pi pos){
ll ptr = 0;
for(ll i = 0;i < s.size();++i){
ll ch = s[i] - 'A';
if(tr[ptr].nxt[ch] == -1) return 0;
ptr = tr[ptr].nxt[ch];
}
ll resl = lower_bound(all(tr[ptr].lst),pos.fi) - tr[ptr].lst.begin(),
resr = upper_bound(all(tr[ptr].lst),pos.se) - tr[ptr].lst.begin();
return resr - resl;
}
};
ll n,m;
trie t1(false),t2(true);
vector<string>s;
void solve(){
cin>>n>>m;s.resize(n+1);
for(ll i = 1;i <= n;++i) cin>>s[i];
sort(s.begin()+1,s.end());
for(ll i = 1;i <= n;++i){
t1.add(s[i],i);
reverse(all(s[i]));
t2.add(s[i],i);
}
for(ll i = 1;i <= m;++i){
string p,q; cin>>p>>q;
auto res = t1.get(p);
//cout<<res.fi<<spc<<res.se<<endl;
cout<<t2.query(q,res)<<endl;
}
}
signed main(){
cin.tie(0) -> sync_with_stdio(0);
open();
ll t = 1; //cin>>t;
while(t--) solve();
cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
Compilation message
selling_rna.cpp: In member function 'void trie::add(std::string&, long long int&)':
selling_rna.cpp:47:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(ll i = 0;i < s.size();++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<long long int, long long int> trie::get(std::string&)':
selling_rna.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(ll i = 0;i < s.size();++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'long long int trie::query(std::string&, std::pair<long long int, long long int>)':
selling_rna.cpp:72:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(ll i = 0;i < s.size();++i){
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'void open()':
selling_rna.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen("i.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen("o.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
536 ms |
562064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
