#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
vector<vector<int> > a;
vector<pair<vector<int> , int> > que;
pii rng[maxn];
int to[maxn*2][4];
int lb[maxn*2], rb[maxn*2];
int trieat = 2;
int n,q;
void build(int l, int r, int dep, int ql, int qr){
for (int i = ql; i<=qr; ++i) {
if (que[i].f.size()==dep) {
rng[que[i].s] = {l,r};
}else break;
}
}
map<char, int> mp = {{'A',0},{'G',1},{'C',2},{'U',3}};
vector<int> cv(string s) {
vector<int> re(SZ(s));
for (int i = 0; i<SZ(s); ++i) re[i] = mp[s[i]];
return re;
}
vector<int> stuff[maxn*2];
int add(vector<int> s, int at, int id=-1, bool t1=1) {
for (int i = 0; i<SZ(s); ++i) {
if (to[at][s[i]] == -1) {
to[at][s[i]] = trieat ++;
}
at = to[at][s[i]];
if (t1 && id != -1) {
lb[at] = min(lb[at], id);
rb[at] = max(rb[at], id);
}else if (t1 == 0){
stuff[at].pb(id);
}
}
return at;
}
signed main(){
IOS();
memset(to, -1, sizeof to);
memset(lb, 0x3f, sizeof lb);
memset(rb, -1, sizeof rb);
cin>>n>>q;
int root1 = 0, root2 = 1;
for (int i = 0; i<n; ++i) {
string s; cin>>s;
a.pb(cv(s));
}
sort(ALL(a));
for (int i = 0; i<n; ++i){
add(a[i], 0, i);
vector<int> tmp = a[i]; reverse(ALL(tmp));
add(tmp, 1,i,0);
}
for (int i =0 ; i<trieat; ++i) {
sort(ALL(stuff[i]));
}
for (int i = 0; i<q; ++i) {
string a, b; cin>>a>>b;
reverse(ALL(b));
int tmp = add(cv(a),0);
int L = lb[tmp], R = rb[tmp];
bug(L,R);
int n2 = add(cv(b), 1);
bug(tmp, n2);
int ans = (upper_bound(ALL(stuff[n2]), R) - stuff[n2].begin()) - 1
- (upper_bound(ALL(stuff[n2]), L-1) - stuff[n2].begin() - 1);
cout<<max(0,ans)<<endl;
}
}
Compilation message
selling_rna.cpp: In function 'void build(int, int, int, int, int)':
selling_rna.cpp:62:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (que[i].f.size()==dep) {
~~~~~~~~~~~~~~~^~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:101:9: warning: unused variable 'root1' [-Wunused-variable]
int root1 = 0, root2 = 1;
^~~~~
selling_rna.cpp:101:20: warning: unused variable 'root2' [-Wunused-variable]
int root1 = 0, root2 = 1;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
11 ms |
19200 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 5 |
Correct |
12 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 7 |
Correct |
11 ms |
19072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
147 ms |
80416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
22952 KB |
Output is correct |
| 2 |
Correct |
49 ms |
21560 KB |
Output is correct |
| 3 |
Correct |
53 ms |
22180 KB |
Output is correct |
| 4 |
Correct |
43 ms |
21680 KB |
Output is correct |
| 5 |
Correct |
46 ms |
21560 KB |
Output is correct |
| 6 |
Correct |
65 ms |
22184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
11 ms |
19200 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 5 |
Correct |
12 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 7 |
Correct |
11 ms |
19072 KB |
Output is correct |
| 8 |
Runtime error |
147 ms |
80416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Halted |
0 ms |
0 KB |
- |
