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 pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=(j);i>=(k);i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e6+6;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=123456789;
int n,m;
int node[maxn][4],Time;
vector<int> L[maxn];
string s[maxn];
void Transform(string& s)
{
for(char& c:s)
{
if (c=='U') c='B';
else if (c=='G') c='D';
}
}
void sol()
{
cin >> n>> m;
for1(i,1,n)
{
cin >> s[i];
Transform(s[i]);
}
memset(node,-1,sizeof(node));
sort(s+1,s+1+n);
for1(i,1,n)
{
int cur=0;
string x=s[i];
reverse(all(x));
for(char c:x)
{
if (node[cur][c-'A']==-1) node[cur][c-'A']=++Time;
cur=node[cur][c-'A'];
L[cur].pb(i);
}
}
for1(i,1,m)
{
string p,q;
cin>>p>>q;
Transform(p);
Transform(q);
int l=lower_bound(s+1,s+1+n,p)-s;
p.back()++;
int r=lower_bound(s+1,s+1+n,p)-s-1;
if (r<l)
{
cout << "0\n";
continue;
}
reverse(all(q));
int cur=0;
for(char c:q)
{
cur=node[cur][c-'A'];
if (cur==-1) break;
}
if (cur==-1)
{
cout << "0\n";
continue;
}
cout << upper_bound(all(L[cur]),r)-lower_bound(all(L[cur]),l)<<'\n';
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("PAINT.inp","r",stdin);
// freopen("PAINT.out","w",stdout);
int t=1;//cin>>t;
while (t--)
{
sol();
}
}
/*
*/
# | 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... |