#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k,t) (lower_bound(all(v),(k),t)-v.begin())
#define fi first
#define se second
#define dame(a) {out(a);return 0;}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll sz=4;
vector<string> str;
vector<pair<string,string>> query;
vi ans;
ll char_to_ll(char c){
if(c=='A')return 0;
if(c=='G')return 1;
if(c=='C')return 2;
if(c=='U')return 3;
}
vp stringnum;
vector<pair<P,P>> querynum;
class trie{
public:
vvi ch,q;
vp range;
ll c=1,euler;
vvi res;
trie(ll k){
ch=vvi(1,vi(sz,-1));
res=vvi(1);
}
void insert(ll num){
ll w=0;
rep(i,str[num].size()){
ll t=char_to_ll(str[num][i]);
if(ch[w][t]==-1){
ch[w][t]=c++;
res.pb(vi(0));ch.pb(vi(4,-1));
w=ch[w][t];
}
else{
w=ch[w][t];
}
}
res[w].pb(num);
}
void add_query(ll num){
if(q.size()==0)q=vvi(c);
ll w=0;
rep(i,query[num].fi.size()){
ll t=char_to_ll(query[num].fi[i]);
if(ch[w][t]==-1)return;
else w=ch[w][t];
}
q[w].pb(num);
}
void euler_tour(ll w){
if(range.size()==0){
euler=0;
range=vp(c);
}
range[w].fi=euler++;
rep(i,sz)if(ch[w][i]!=-1)euler_tour(ch[w][i]);
range[w].se=euler;
for(ll x:res[w])stringnum[x].fi=range[w].fi;
for(ll x:q[w])querynum[x].fi=range[w];
}
};
class rtrie{
public:
vvi ch,q;
vp range;
ll c=1,euler;
vvi res;
rtrie(ll k){
ch=vvi(1,vi(sz,-1));
res=vvi(1);
}
void insert(ll num){
ll w=0;
for(int i=str[num].size()-1;i>=0;i--){
ll t=char_to_ll(str[num][i]);
if(ch[w][t]==-1){
ch[w][t]=c++;
res.pb(vi(0));ch.pb(vi(4,-1));
w=ch[w][t];
}
else{
w=ch[w][t];
}
}
res[w].pb(num);
}
void add_query(ll num){
if(q.size()==0)q=vvi(c);
ll w=0;
for(int i=query[num].se.size()-1;i>=0;i--){
ll t=char_to_ll(query[num].se[i]);
if(ch[w][t]==-1)return;
else w=ch[w][t];
}
q[w].pb(num);
}
void euler_tour(ll w){
if(range.size()==0){
euler=0;
range=vp(c);
}
range[w].fi=euler++;
rep(i,sz)if(ch[w][i]!=-1)euler_tour(ch[w][i]);
range[w].se=euler;
for(ll x:res[w])stringnum[x].se=range[w].fi;
for(ll x:q[w])querynum[x].se=range[w];
}
};
bool comp_y(P a,P b){
if(a.se==b.se)return a.fi<b.fi;
return a.se<b.se;
}
class fractional_cascading{
public:
ll N=1;vvp seg;
vi L,R;
fractional_cascading(vp v){
sort(all(v));
while(N<v.size())N*=2;
seg=vvp(N*2-1);L=vi(N*2-1,inf);R=vi(N*2-1,-inf);
rep(i,v.size())seg[i+N-1].pb(v[i]);
rep(i,N)L[i+N-1]=R[i+N-1]=v[min(i,(ll)(v.size()-1))].fi;
rep(i,N)R[i+N-1]++;
for(int i=N-2;i>=0;i--){
L[i]=L[i*2+1];R[i]=R[i*2+2];
int a=0,b=0;
while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
if(b==seg[i*2+2].size())seg[i].pb(seg[i*2+1][a++]);
else if(a==seg[i*2+1].size())seg[i].pb(seg[i*2+2][b++]);
else if(comp_y(seg[i*2+1][a],seg[i*2+2][b]))seg[i].pb(seg[i*2+1][a++]);
else seg[i].pb(seg[i*2+2][b++]);
}
}
}
ll range_sum(ll x1,ll x2,ll y1,ll y2,ll k=0){
// cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<' '<<k<<endl;
if(x1<=L[k]&&R[k]<=x2)return lb(seg[k],P(-inf,y2),comp_y)-lb(seg[k],P(-inf,y1),comp_y);
if(R[k]<=x1||x2<=L[k])return 0;
return range_sum(x1,x2,y1,y2,k*2+1)+range_sum(x1,x2,y1,y2,k*2+2);
}
};
int main(){
ll n,m;cin>>n>>m;
str=vector<string>(n);
query=vector<pair<string,string>>(m);
stringnum=vp(n);querynum=vector<pair<P,P>>(m);
ans=vi(m);
rep(i,n)cin>>str[i];
rep(i,m)cin>>query[i].fi>>query[i].se;
trie tr(1);
rtrie rtr(1);
rep(i,n){
tr.insert(i);
rtr.insert(i);
}
rep(i,m){
tr.add_query(i);
rtr.add_query(i);
}
tr.euler_tour(0);rtr.euler_tour(0);
fractional_cascading fac(stringnum);
rep(i,m)out(fac.range_sum(querynum[i].fi.fi,querynum[i].fi.se,querynum[i].se.fi,querynum[i].se.se));
}
Compilation message
selling_rna.cpp: In constructor 'fractional_cascading::fractional_cascading(vp)':
selling_rna.cpp:147:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | while(N<v.size())N*=2;
| ~^~~~~~~~~
selling_rna.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:155:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:156:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | if(b==seg[i*2+2].size())seg[i].pb(seg[i*2+1][a++]);
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:157:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | else if(a==seg[i*2+1].size())seg[i].pb(seg[i*2+2][b++]);
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'll char_to_ll(char)':
selling_rna.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
40 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
510 ms |
269748 KB |
Output is correct |
2 |
Correct |
507 ms |
258380 KB |
Output is correct |
3 |
Correct |
513 ms |
267836 KB |
Output is correct |
4 |
Correct |
499 ms |
256124 KB |
Output is correct |
5 |
Correct |
650 ms |
331892 KB |
Output is correct |
6 |
Correct |
653 ms |
337132 KB |
Output is correct |
7 |
Correct |
166 ms |
10476 KB |
Output is correct |
8 |
Correct |
516 ms |
201432 KB |
Output is correct |
9 |
Correct |
468 ms |
170380 KB |
Output is correct |
10 |
Correct |
372 ms |
163468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
120 ms |
30948 KB |
Output is correct |
2 |
Correct |
101 ms |
18920 KB |
Output is correct |
3 |
Correct |
114 ms |
27236 KB |
Output is correct |
4 |
Correct |
99 ms |
23204 KB |
Output is correct |
5 |
Correct |
83 ms |
18792 KB |
Output is correct |
6 |
Correct |
108 ms |
27236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
510 ms |
269748 KB |
Output is correct |
9 |
Correct |
507 ms |
258380 KB |
Output is correct |
10 |
Correct |
513 ms |
267836 KB |
Output is correct |
11 |
Correct |
499 ms |
256124 KB |
Output is correct |
12 |
Correct |
650 ms |
331892 KB |
Output is correct |
13 |
Correct |
653 ms |
337132 KB |
Output is correct |
14 |
Correct |
166 ms |
10476 KB |
Output is correct |
15 |
Correct |
516 ms |
201432 KB |
Output is correct |
16 |
Correct |
468 ms |
170380 KB |
Output is correct |
17 |
Correct |
372 ms |
163468 KB |
Output is correct |
18 |
Correct |
120 ms |
30948 KB |
Output is correct |
19 |
Correct |
101 ms |
18920 KB |
Output is correct |
20 |
Correct |
114 ms |
27236 KB |
Output is correct |
21 |
Correct |
99 ms |
23204 KB |
Output is correct |
22 |
Correct |
83 ms |
18792 KB |
Output is correct |
23 |
Correct |
108 ms |
27236 KB |
Output is correct |
24 |
Correct |
519 ms |
232180 KB |
Output is correct |
25 |
Correct |
590 ms |
236408 KB |
Output is correct |
26 |
Correct |
493 ms |
228220 KB |
Output is correct |
27 |
Correct |
506 ms |
229364 KB |
Output is correct |
28 |
Correct |
683 ms |
104244 KB |
Output is correct |
29 |
Correct |
376 ms |
65984 KB |
Output is correct |