#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
//const int M = 2e6 + 5;
const int oo = 1e9;
int n, m;
string s[N], a[N], b[N];
char change(char c){
if(c == 'A') return '1';
if(c == 'C') return '2';
if(c == 'G') return '3';
return '4';
}
struct trie{
trie* child[8];
vector<int> w;
trie(){
for(int i = 1; i <= 4; i ++) child[i] = NULL;
w.clear();
}
};
trie* root;
void add(string &x,int id){
trie* p = root;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) p -> child[val] = new trie();
p = p -> child[val];
p -> w.push_back(id);
}
}
int query(string &x,int l,int r){
trie* p = root;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) return 0;
p = p -> child[val];
}
auto v = upper_bound(p -> w.begin(), p -> w.end(), r);
auto u = lower_bound(p -> w.begin(), p -> w.end(), l);
if(v == p -> w.begin()) return 0;
if(u == p -> w.end()) return 0;
v--;
int tu = u - p -> w.begin();
int tv = v - p -> w.begin();
if(tu <= tv) return tv - tu + 1;
return 0;
}
struct tree{
tree* child[8];
int mx, mi;
tree(){
for(int i = 1; i <= 4; i ++) child[i] = NULL;
mx = 0, mi = n + 1;
}
};
tree* wr;
void update(string &x,int id){
tree* p = wr;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) p -> child[val] = new tree();
p = p -> child[val];
p -> mx = max(p -> mx, id);
p -> mi = min(p -> mi, id);
}
}
pair<int,int> get(string &x){
tree* p = wr;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) return {0, 0};
p = p -> child[val];
}
return {p -> mi, p -> mx};
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
root = new trie();
wr = new tree();
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> s[i];
for(int j = 0; j < s[i].size(); j ++){
s[i][j] = change(s[i][j]);
}
}
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i ++){
update(s[i], i);
string hk = s[i];
reverse(hk.begin(), hk.end());
add(hk, i);
}
for(int i = 1; i <= m; i ++){
cin >> a[i] >> b[i];
for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
pair<int,int> kq = get(a[i]);
if(!kq.first){
cout << 0 << "\n";
continue;
}
reverse(b[i].begin(), b[i].end());
cout << query(b[i], kq.first, kq.second) << "\n";
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int j = 0; j < s[i].size(); j ++){
| ~~^~~~~~~~~~~~~
selling_rna.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
| ~~^~~~~~~~~~~~~
selling_rna.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
| ~~^~~~~~~~~~~~~
selling_rna.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
19024 KB |
Output is correct |
2 |
Correct |
4 ms |
19280 KB |
Output is correct |
3 |
Correct |
3 ms |
19280 KB |
Output is correct |
4 |
Correct |
3 ms |
19124 KB |
Output is correct |
5 |
Correct |
3 ms |
19024 KB |
Output is correct |
6 |
Correct |
3 ms |
19120 KB |
Output is correct |
7 |
Correct |
4 ms |
19024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
242 ms |
269896 KB |
Output is correct |
2 |
Correct |
245 ms |
256464 KB |
Output is correct |
3 |
Correct |
165 ms |
188228 KB |
Output is correct |
4 |
Correct |
154 ms |
182600 KB |
Output is correct |
5 |
Correct |
242 ms |
272012 KB |
Output is correct |
6 |
Correct |
250 ms |
275720 KB |
Output is correct |
7 |
Correct |
57 ms |
38996 KB |
Output is correct |
8 |
Correct |
188 ms |
182280 KB |
Output is correct |
9 |
Correct |
166 ms |
158536 KB |
Output is correct |
10 |
Correct |
146 ms |
149880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
19916 KB |
Output is correct |
2 |
Correct |
17 ms |
20296 KB |
Output is correct |
3 |
Correct |
21 ms |
20016 KB |
Output is correct |
4 |
Correct |
15 ms |
19904 KB |
Output is correct |
5 |
Correct |
17 ms |
20376 KB |
Output is correct |
6 |
Correct |
20 ms |
20216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
19024 KB |
Output is correct |
2 |
Correct |
4 ms |
19280 KB |
Output is correct |
3 |
Correct |
3 ms |
19280 KB |
Output is correct |
4 |
Correct |
3 ms |
19124 KB |
Output is correct |
5 |
Correct |
3 ms |
19024 KB |
Output is correct |
6 |
Correct |
3 ms |
19120 KB |
Output is correct |
7 |
Correct |
4 ms |
19024 KB |
Output is correct |
8 |
Correct |
242 ms |
269896 KB |
Output is correct |
9 |
Correct |
245 ms |
256464 KB |
Output is correct |
10 |
Correct |
165 ms |
188228 KB |
Output is correct |
11 |
Correct |
154 ms |
182600 KB |
Output is correct |
12 |
Correct |
242 ms |
272012 KB |
Output is correct |
13 |
Correct |
250 ms |
275720 KB |
Output is correct |
14 |
Correct |
57 ms |
38996 KB |
Output is correct |
15 |
Correct |
188 ms |
182280 KB |
Output is correct |
16 |
Correct |
166 ms |
158536 KB |
Output is correct |
17 |
Correct |
146 ms |
149880 KB |
Output is correct |
18 |
Correct |
21 ms |
19916 KB |
Output is correct |
19 |
Correct |
17 ms |
20296 KB |
Output is correct |
20 |
Correct |
21 ms |
20016 KB |
Output is correct |
21 |
Correct |
15 ms |
19904 KB |
Output is correct |
22 |
Correct |
17 ms |
20376 KB |
Output is correct |
23 |
Correct |
20 ms |
20216 KB |
Output is correct |
24 |
Correct |
230 ms |
228936 KB |
Output is correct |
25 |
Correct |
259 ms |
229408 KB |
Output is correct |
26 |
Correct |
217 ms |
226376 KB |
Output is correct |
27 |
Correct |
158 ms |
161620 KB |
Output is correct |
28 |
Correct |
131 ms |
63560 KB |
Output is correct |
29 |
Correct |
58 ms |
27720 KB |
Output is correct |