#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int N = (int)2e6+10;
vector<int> xd[N];
int trie[2][4][N];
int L[N], R[N];
int n, m, I[2];
string s[N];
void add(string &s, int j, int t, bool r=0){
int v = 1;
for(int i = 0; i < sz(s); i++){
char u = s[r?sz(s)-1-i:i];
int c = (u=='A'?0:u=='C'?1:u=='G'?2:3);
if(!trie[t][c][v]) trie[t][c][v]=I[t]++;
v = trie[t][c][v];
if(!t){
if(!L[v]) L[v]=j;
R[v]=max(R[v],j);
}
else xd[v].push_back(j);
}
}
int get(string &s, int t, bool r=0){
int v = 1;
for(int i = 0; i < sz(s); i++){
char u = s[r?sz(s)-1-i:i];
int c = (u=='A'?0:u=='C'?1:u=='G'?2:3);
v = trie[t][c][v]; if(!v) return 0;
}
return v;
}
int32_t main()
{
cin >> n >> m; I[0]=I[1]=2;
for(int i = 0; i < n; i++)
cin >> s[i]; sort(s,s+n);
for(int i = 0; i < n; i++)
add(s[i],i+1,0),add(s[i],i+1,1,1);
for(int i = 0; i < m; i++){
string s, t; cin >> s >> t;
int ind = get(s,0), ind2=get(t,1,1);
int l = L[ind], r=R[ind];
int pos1 = lower_bound(all(xd[ind2]),l)-begin(xd[ind2]);
int pos2 = upper_bound(all(xd[ind2]),r)-begin(xd[ind2]);
cout << max(0, pos2-pos1) << "\n";
}
}
Compilation message
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
40 | for(int i = 0; i < n; i++)
| ^~~
selling_rna.cpp:41:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
41 | cin >> s[i]; sort(s,s+n);
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
109900 KB |
Output is correct |
2 |
Correct |
45 ms |
109900 KB |
Output is correct |
3 |
Correct |
47 ms |
109884 KB |
Output is correct |
4 |
Correct |
46 ms |
109852 KB |
Output is correct |
5 |
Correct |
50 ms |
109900 KB |
Output is correct |
6 |
Correct |
46 ms |
109916 KB |
Output is correct |
7 |
Correct |
46 ms |
109884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
205232 KB |
Output is correct |
2 |
Correct |
230 ms |
200340 KB |
Output is correct |
3 |
Correct |
196 ms |
169632 KB |
Output is correct |
4 |
Correct |
160 ms |
167292 KB |
Output is correct |
5 |
Correct |
212 ms |
197524 KB |
Output is correct |
6 |
Correct |
193 ms |
198840 KB |
Output is correct |
7 |
Correct |
161 ms |
120464 KB |
Output is correct |
8 |
Correct |
224 ms |
155844 KB |
Output is correct |
9 |
Correct |
253 ms |
156324 KB |
Output is correct |
10 |
Correct |
177 ms |
155228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
110768 KB |
Output is correct |
2 |
Correct |
98 ms |
110668 KB |
Output is correct |
3 |
Correct |
119 ms |
110736 KB |
Output is correct |
4 |
Correct |
104 ms |
110520 KB |
Output is correct |
5 |
Correct |
98 ms |
110776 KB |
Output is correct |
6 |
Correct |
114 ms |
110720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
109900 KB |
Output is correct |
2 |
Correct |
45 ms |
109900 KB |
Output is correct |
3 |
Correct |
47 ms |
109884 KB |
Output is correct |
4 |
Correct |
46 ms |
109852 KB |
Output is correct |
5 |
Correct |
50 ms |
109900 KB |
Output is correct |
6 |
Correct |
46 ms |
109916 KB |
Output is correct |
7 |
Correct |
46 ms |
109884 KB |
Output is correct |
8 |
Correct |
214 ms |
205232 KB |
Output is correct |
9 |
Correct |
230 ms |
200340 KB |
Output is correct |
10 |
Correct |
196 ms |
169632 KB |
Output is correct |
11 |
Correct |
160 ms |
167292 KB |
Output is correct |
12 |
Correct |
212 ms |
197524 KB |
Output is correct |
13 |
Correct |
193 ms |
198840 KB |
Output is correct |
14 |
Correct |
161 ms |
120464 KB |
Output is correct |
15 |
Correct |
224 ms |
155844 KB |
Output is correct |
16 |
Correct |
253 ms |
156324 KB |
Output is correct |
17 |
Correct |
177 ms |
155228 KB |
Output is correct |
18 |
Correct |
123 ms |
110768 KB |
Output is correct |
19 |
Correct |
98 ms |
110668 KB |
Output is correct |
20 |
Correct |
119 ms |
110736 KB |
Output is correct |
21 |
Correct |
104 ms |
110520 KB |
Output is correct |
22 |
Correct |
98 ms |
110776 KB |
Output is correct |
23 |
Correct |
114 ms |
110720 KB |
Output is correct |
24 |
Correct |
253 ms |
188632 KB |
Output is correct |
25 |
Correct |
287 ms |
188728 KB |
Output is correct |
26 |
Correct |
231 ms |
187692 KB |
Output is correct |
27 |
Correct |
193 ms |
160612 KB |
Output is correct |
28 |
Correct |
339 ms |
131788 KB |
Output is correct |
29 |
Correct |
248 ms |
115260 KB |
Output is correct |