This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int maxn=2e5+7;
const int maxx=2e6+7;
string s[maxn];
int n,m;
struct trie
{
int t[maxn][27];
vector<int>who[maxn];
int cnt;
trie(){
cnt=0;
}
void add(string &s,int i){
int curr=0;
for(char c:s){
if(t[curr][c-'a'+1]==0)t[curr][c-'a'+1]=++cnt;
curr=t[curr][c-'a'+1];
who[curr].push_back(i);
}
}
array<int,2>get(string &s){
int curr=0;
for(char c:s){
if(t[curr][c-'a'+1]==0)return {-1,-1};
curr=t[curr][c-'a'+1];
}
return array<int,2>{who[curr].front(),who[curr].back()};
}
int query(string &s,int l,int r){
int curr=0;
for(char c:s){
if(t[curr][c-'a'+1]==0)return 0;
curr=t[curr][c-'a'+1];
}
return (int)(upper_bound(all(who[curr]),r)-lower_bound(all(who[curr]),l));
}
};
trie t,tn;
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
vector<string>s(n);
for(string &s:s){
cin>>s;
}
sort(s.begin(),s.end());
for(int i=0;i<s.size();i++){
t.add(s[i],i);
reverse(all(s[i]));
tn.add(s[i],i);
}
for(int i=1;i<=m;i++){
string p,q;
cin>>p>>q;
reverse(all(q));
auto [L,R]=t.get(p);
cout<<tn.query(q,L,R)<<"\n";
}
return 0;
}
Compilation message (stderr)
selling_rna.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
43 | main()
| ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:52:18: 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]
52 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
selling_rna.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | auto [L,R]=t.get(p);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |