#include <bits/stdc++.h>
#define here cerr<<"=============================\n"
#define ll long long
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define sz(a) (ll)(a.size())
#define pb push_back
#define llinf 100000000000000000LL
#define endl '\n'
#define pll pair<ll,ll>
#define all(a) a.begin(),a.end()
#define fi first
#define sc second
using namespace std;
#define maxn 2000005
#define maxx 30
ll n,q;
ll t[maxn][30];
ll t2[maxn],ls[maxn],rs[maxn];
ll L[maxn],L2[maxn],R[maxn],R2[maxn];
ll root,root2,root3;
ll ti = 0,tsz = 1;
ll lid[maxn],rid[maxn];
ll in[maxn],out[maxn];
vector<ll> a[maxn];
vector<pll> v[maxn];
string ss[maxn];
void add(ll &v,string &s,ll i){
if(!v) v = ++tsz;
if(sz(s)==i) return;
ll c = s[i]-'A';
add(t[v][c],s,i+1);
}
void dfs(ll v){
in[v] = ++ti;
for(ll i = 0;i<27;i++){
if(!t[v][i]) continue;
dfs(t[v][i]);
}
out[v] = ti;
}
pll get(ll v,string s,ll i){
if(sz(s)==i) return {in[v],out[v]};
ll c = s[i]-'A';
if(t[v][c]==0) return {-1,-2};
return get(t[v][c],s,i+1);
}
void upd(ll v,ll tl,ll tr,ll i,ll x){
if(tl==tr){t2[v]+=x;return;}
ll mid = (tl+tr)/2;
if(i<=mid) upd(ls[v],tl,mid,i,x);
else upd(rs[v],mid+1,tr,i,x);
t2[v] = t2[ls[v]] + t2[rs[v]];
}
ll sum(ll v,ll tl,ll tr,ll l,ll r){
if(l>r||tl>tr||tr<l||tl>r) return 0;
if(tl>=l&&tr<=r) return t2[v];
ll mid = (tl+tr)/2;
return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r);
}
void init(ll &v,ll tl,ll tr){
if(!v) v = ++tsz;
if(tl==tr) return;
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
}
struct kv{
ll l,r,d;
};
bool operator < (kv a,kv b){
return a.d<b.d;
}
map<pair<pll,ll> ,ll> mp;
int main()
{
cin >> n >> q;
root = 1;
root2 = 1;
for(ll i = 1;i<=n;i++){
string s; cin >> ss[i];
s = ss[i];
add(root,s,0);
}
dfs(root);
root2 = ++tsz;
for(ll i = 1;i<=n;i++){
string s = ss[i];
reverse(all(s));
add(root2,s,0);
}
ti = 0;
dfs(root2);
ll mx = tsz;
for(ll i = 1;i<=n;i++){
string s = ss[i];
pll p = get(root,s,0);
lid[i] = p.fi;
reverse(all(s));
p = get(root2,s,0);
rid[i] = p.fi;
a[rid[i]].pb(lid[i]);
}
for(ll i = 1;i<=q;i++){
string s; cin >> s;
pll p = get(root,s,0);
cin >> s;
L[i] = p.fi,R[i] = p.sc;
reverse(all(s));
p = get(root2,s,0);
L2[i] = p.fi,R2[i] = p.sc;
v[L2[i]-1].pb({L[i],R[i]});
v[R2[i]].pb({L[i],R[i]});
}
tsz = root3 = 0;
init(root3,1,mx);
for(ll i = 0;i<=mx;i++){
for(ll x : a[i]){
upd(root3,1,mx,x,1);
}
for(pll p : v[i]){
mp[{{p.fi,p.sc},i}] = sum(root3,1,mx,p.fi,p.sc);
}
}
for(ll i = 1;i<=q;i++){
cout<<mp[{{L[i],R[i]},R2[i]}] - mp[{{L[i],R[i]},L2[i]-1}]<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
156984 KB |
Output is correct |
| 2 |
Correct |
68 ms |
156972 KB |
Output is correct |
| 3 |
Correct |
74 ms |
156924 KB |
Output is correct |
| 4 |
Correct |
70 ms |
156908 KB |
Output is correct |
| 5 |
Correct |
70 ms |
157032 KB |
Output is correct |
| 6 |
Correct |
70 ms |
157004 KB |
Output is correct |
| 7 |
Correct |
77 ms |
156940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1617 ms |
679788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
162588 KB |
Output is correct |
| 2 |
Correct |
120 ms |
161780 KB |
Output is correct |
| 3 |
Correct |
130 ms |
162116 KB |
Output is correct |
| 4 |
Correct |
107 ms |
160612 KB |
Output is correct |
| 5 |
Correct |
140 ms |
161968 KB |
Output is correct |
| 6 |
Correct |
126 ms |
162360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
156984 KB |
Output is correct |
| 2 |
Correct |
68 ms |
156972 KB |
Output is correct |
| 3 |
Correct |
74 ms |
156924 KB |
Output is correct |
| 4 |
Correct |
70 ms |
156908 KB |
Output is correct |
| 5 |
Correct |
70 ms |
157032 KB |
Output is correct |
| 6 |
Correct |
70 ms |
157004 KB |
Output is correct |
| 7 |
Correct |
77 ms |
156940 KB |
Output is correct |
| 8 |
Execution timed out |
1617 ms |
679788 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
