#include<bits/stdc++.h>
using namespace std;
struct rect
{
int xl,xr,yl,yr;
rect() {}
};
struct node
{
char let;
int l,r;
node* c[27];
vector<int> idx,qr;
node()
{
for(int i=0; i<26; i++)
c[i]=nullptr;
}
};
node* pf=new node();
node* sf=new node();
int n,m;
string s[100001],pq[100001],sq[100001];
pair<int,int> p[100001];
rect q[100001];
void add(string x,int z,int t)
{
node* curr=pf;
for(int i=0; i<x.size(); i++)
{
int y=(int)(x[i]-'A');
if(curr->c[y]==nullptr)
{
if(t==2)return;
curr->c[y]=new node();
}
curr=curr->c[y];
curr->let=x[i];
}
if(t==1)curr->idx.push_back(z);
else curr->qr.push_back(z);
curr=sf;
for(int i=x.size()-1; i>=0; i--)
{
int y=x[i]-'A';
if(curr->c[y]==nullptr)
curr->c[y]=new node();
curr=curr->c[y];
curr->let=x[i];
}
curr->idx.push_back(z);
}
int num;
void dfs(node* i,int t)
{
//cout<<i->let<<endl;
num++;
i->l=num;
for(int j=0; j<i->idx.size(); j++)
{
if(t==1)p[i->idx[j]].first=num;
else p[i->idx[j]].second=num;
}
for(int j=0; j<26; j++)
{
if(i->c[j]!=nullptr)
{
dfs(i->c[j],t);
}
}
//cout<<"out"<<endl;
i->r=num;
for(int j=0; j<i->qr.size(); j++)
{
if(t==1)
{
q[i->qr[j]].xl=i->l;
q[i->qr[j]].xr=i->r;
}
else
{
q[i->qr[j]].yl=i->l;
q[i->qr[j]].yr=i->r;
}
}
}
void read()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>s[i];
add(s[i],i,1);
}
for(int i=1; i<=m; i++)
{
cin>>pq[i]>>sq[i];
node* curr=pf;
for(int j=0; j<pq[i].size(); j++)
{
int y=(int)(pq[i][j]-'A');
if(curr->c[y]==nullptr)
break;
curr=curr->c[y];
if(j==pq[i].size()-1)
curr->qr.push_back(i);
}
reverse(sq[i].begin(),sq[i].end());
curr=sf;
for(int j=0; j<sq[i].size(); j++)
{
int y=(int)(sq[i][j]-'A');
if(curr->c[y]==nullptr)
break;
curr=curr->c[y];
if(j==sq[i].size()-1)
curr->qr.push_back(i);
}
}
}
bool cmp(pair<int,int> p1,pair<int,int> p2)
{
return p1.second<p2.second;
}
struct line
{
int l,r,y,i,mt;
line(){}
line(int _l,int _r,int _y,int _i,int _mt)
{
l=_l;
r=_r;
y=_y;
i=_i;
mt=_mt;
}
};
vector<line> v;
bool cmp2(line l1,line l2)
{
return l1.y<l2.y;
}
int t[9000001];
void update(int i,int l,int r,int idx)
{
if(l==r)
{
t[i]++;
return;
}
int md=(l+r)/2;
if(idx<=md)update(i*2,l,md,idx);
else update(i*2+1,md+1,r,idx);
t[i]=t[i*2]+t[i*2+1];
}
int query(int i,int l,int r,int ql,int qr)
{
//cout<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
if(ql>qr)return 0;
if(ql<=l&&r<=qr)return t[i];
int md=(l+r)/2;
return query(i*2,l,md,ql,min(qr,md))+query(i*2+1,md+1,r,max(md+1,ql),qr);
}
int ans[100001];
void solve()
{
sort(p+1,p+n+1,cmp);
for(int i=1;i<=m;i++)
{
if(q[i].xl==0||q[i].yl==0)continue;
v.push_back({q[i].xl,q[i].xr,q[i].yl-1,i,-1});
v.push_back({q[i].xl,q[i].xr,q[i].yr,i,1});
}
sort(v.begin(),v.end(),cmp2);
int j=1;
for(int i=0;i<v.size();i++)
{
line l=v[i];
while(j<=n&&p[j].second<=l.y)
{
//cout<<j<<endl;
update(1,1,2*1e6+5,p[j].first);
j++;
}
ans[l.i]=l.mt*query(1,1,2*1e6+5,l.l,l.r);
}
for(int i=1;i<=m;i++)
cout<<ans[i]<<endl;
}
int main()
{
read();
dfs(pf,1);
num=0;
dfs(sf,2);
/*
for(int i=1; i<=n; i++)
cout<<p[i].first<<" "<<p[i].second<<endl;
for(int i=1; i<=m; i++)
cout<<q[i].xl<<" "<<q[i].xr<<" "<<q[i].yl<<" "<<q[i].yr<<endl;
*/
solve();
return 0;
}
Compilation message
selling_rna.cpp: In function 'void add(std::string, int, int)':
selling_rna.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0; i<x.size(); i++)
| ~^~~~~~~~~
selling_rna.cpp: In function 'void dfs(node*, int)':
selling_rna.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j=0; j<i->idx.size(); j++)
| ~^~~~~~~~~~~~~~
selling_rna.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int j=0; j<i->qr.size(); j++)
| ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void read()':
selling_rna.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=0; j<pq[i].size(); j++)
| ~^~~~~~~~~~~~~
selling_rna.cpp:123:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if(j==pq[i].size()-1)
| ~^~~~~~~~~~~~~~~~
selling_rna.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j=0; j<sq[i].size(); j++)
| ~^~~~~~~~~~~~~
selling_rna.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | if(j==sq[i].size()-1)
| ~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
578476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22760 KB |
Output is correct |
| 2 |
Incorrect |
60 ms |
16856 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
