#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxm=6e6+5;
map<char,int>m;
struct node{
int a[4];
int cnt=0;
node(){for(int i=0;i<4;i++)a[i]=0;}
};
vector<node>trie[2];
int tin[2][maxm];
int tout[2][maxm];
int vt[2][maxm];
void add(string s,int id,int type){
int pos=0;
for(auto &v:s){
int k=m[v];
if(trie[type][pos].a[k]==0){
trie[type][pos].a[k]=trie[type].size();
trie[type].pb(node());
}
pos=trie[type][pos].a[k];
}
vt[type][id]=pos;
}
int s[2];
void dfs(int id,int type){
tin[type][id]=++s[type];
for(int pos=0;pos<4;pos++){
if(trie[type][id].a[pos]!=0){
dfs(trie[type][id].a[pos],type);
}
}
tout[type][id]=s[type];
}
int n;
string p[2][maxn];
vector<int>Upd[maxm];
vector<int>poi;
int bit[maxn];
void update(int id,int val){
for(int i=id;i<=n;i+=i&(-i)){
bit[i]+=val;
}
}
int get(int id){
int res=0;
for(int i=id;i>=1;i-=i&(-i)){
res+=bit[i];
}
return res;
}
int getrange(int l,int r){
return get(r)-get(l-1);
}
vector<pair<int,int>>P[maxm];
int ans[maxn];
int po2[maxn];
signed main(){
freopen("input.inp","r",stdin);
freopen("output.out","w",stdout);
cin.tie(0),cout.tie(0)->sync_with_stdio(0);
cin >> n;
int q;
cin >> q;
trie[0].pb(node());
trie[1].pb(node());
m['A']=0;
m['G']=1;
m['C']=2;
m['U']=3;
for(int i=1;i<=n;i++){
cin >> p[0][i];
p[1][i]=p[0][i];
reverse(p[1][i].begin(),p[1][i].end());
add(p[0][i],i,0);
add(p[1][i],i,1);
}
dfs(0,0);
dfs(0,1);
for(int i=1;i<=n;i++){
poi.pb(tin[1][vt[1][i]]);
Upd[tin[0][vt[0][i]]].pb(tin[1][vt[1][i]]);
}
sort(poi.begin(),poi.end());
poi.resize(unique(poi.begin(),poi.end())-poi.begin());
for(int i=1;i<=q;i++){
string s;
string p;
int pos1=0;
cin >> s >> p;
bool loai=0;
reverse(p.begin(),p.end());
for(int j=0;j<(int)s.size();j++){
if(trie[0][pos1].a[m[s[j]]]==0){
loai=1;
break;
}
else{
pos1=trie[0][pos1].a[m[s[j]]];
}
}
int pos2=0;
for(int j=0;j<(int)p.size();j++){
if(trie[1][pos2].a[m[p[j]]]==0){
loai=1;
break;
}
else{
pos2=trie[1][pos2].a[m[p[j]]];
}
}
if(loai==0){
P[tin[0][pos1]-1].pb({i,-1});
P[tout[0][pos1]].pb({i,1});
po2[i]=pos2;
}
}
for(int i=1;i<=s[0];i++){
for(auto id:Upd[i]){
int st=lower_bound(poi.begin(),poi.end(),id)-poi.begin()+1;
update(st,1);
}
for(auto v:P[i]){
int id=v.fi;
int mul=v.se;
int x=lower_bound(poi.begin(),poi.end(),tin[1][po2[id]])-poi.begin()+1;
int y=upper_bound(poi.begin(),poi.end(),tout[1][po2[id]])-poi.begin();
// cout << x << ' ' << y << '\n';
ans[id]+=getrange(x,y)*mul;
}
}
for(int i=1;i<=q;i++){
cout << ans[i] << '\n';
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:65:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | freopen("input.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:66:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | freopen("output.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
288484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
288424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
288480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
288484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
