#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;
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:154: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]
154 | while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:154: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]
154 | while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:155: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]
155 | if(b==seg[i*2+2].size())seg[i].pb(seg[i*2+1][a++]);
| ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:156: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]
156 | 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 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
520 ms |
269748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
30820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
