#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
int ndcnt = 0;
const int MAXN = 2e6+5;
int ch[4][MAXN];
vector<int>ids[MAXN],que[MAXN],pts[MAXN];
int tin[MAXN],tout[MAXN];
pii pt[MAXN];
void add(string s,int id){
int v = 0;
for(char x:s){
int c = 0;
if(x=='C')c=1;
if(x=='G')c=2;
if(x=='U')c=3;
if(!ch[c][v])ch[c][v] = ++ndcnt;
v = ch[c][v];
}
ids[v].push_back(id);
}
int timer = 1;
void dfs(int v){
tin[v] = ++timer;
for(int i=0;i<4;i++){
if(ch[i][v])dfs(ch[i][v]);
}
tout[v] = timer;
for(int x:ids[v]){
if(x>0)pt[x].fi = tin[v];
else pt[-x].se = tin[v];
}
}
int find(string s){
int v = 0;
for(char x:s){
int c = 0;
if(x=='C')c=1;
if(x=='G')c=2;
if(x=='U')c=3;
if(!ch[c][v])return -1;
v = ch[c][v];
}
return v;
}
int bit[MAXN];
void upd(int pos,int val,int n){
for(int i=pos;i<=n;i+=i&(-i))bit[i]+=val;
}
int query(int r){
int res = 0;
for(int i=r;i>0;i-=i&(-i))res+=bit[i];
return res;
}
int main()
{
owo
int n,m;
cin>>n>>m;
vector<string>s(n+1);
vector<int>ans(m+1,0),l(m+1),r(m+1);
for(int i=1;i<=n;i++){
cin>>s[i];
add(s[i],i);
reverse(s[i].begin(),s[i].end());
add(s[i],-i);
}
dfs(0);
//cout<<"pts"<<'\n';
for(int i=1;i<=n;i++){
//cout<<pt[i].fi<<" "<<pt[i].se<<'\n';
pts[pt[i].fi].push_back(pt[i].se);
}
//cout<<"frange"<<'\n';
for(int i=1;i<=m;i++){
string p,q;
cin>>p>>q;
int v1 = find(p);
reverse(q.begin(),q.end());
int v2 = find(q);
//cout<<p<<" "<<q<<'\n';
if(v1==-1 || v2==-1)continue;
//cout<<v1<<" "<<v2<<'\n';
//cout<<i<<" "<<tin[v1]<<" "<<tout[v1]<<" "<<tin[v2]<<" "<<tout[v2]<<'\n';
l[i] = tin[v2]-1;
r[i] = tout[v2];
que[tin[v1]-1].push_back(-i);
que[tout[v1]].push_back(i);
}
for(int i=1;i<=timer;i++){
for(int x:pts[i])upd(x,1,timer);
for(int x:que[i]){
int c = query(r[abs(x)]) - query(l[abs(x)]);
if(x>0)ans[x]+=c;
else ans[x]-=c;
}
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
170 ms |
286284 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
373 ms |
399320 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
145416 KB |
Output is correct |
| 2 |
Runtime error |
210 ms |
291792 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
170 ms |
286284 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
