#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
int n, m;
string s[N], t[N];
int toint[200];
struct node {
int to[4];
int ind, l, r, pr;
node() {
l = N;
r = 0;
memset(to, -1, sizeof to);
}
};
node st[(int)2e6 + 7];
int ar[N];
int sz;
int add(string &t, int j) {
int cur = 0;
for (int i = 0; i < t.size(); i++) {
if (st[cur].to[toint[t[i]]] == -1) {
st[cur].to[toint[t[i]]] = ++sz;
st[sz].pr = cur;
}
cur = st[cur].to[toint[t[i]]];
}
reverse(t.begin(), t.end());
st[cur].ind = lower_bound(s + 1, s + n + 1, t) - s;
reverse(t.begin(), t.end());
int temp = cur;
while (cur) {
st[cur].r = max(st[cur].r, j);
st[cur].l = min(st[cur].l, j);
cur = st[cur].pr;
}
return st[temp].ind;
}
int root[N];
struct seg {
int l, r, val;
seg() {
l = r = val = 0;
}
};
seg tree[N * 30];
void build(int v = 1, int l = 1, int r = n) {
tree[v].val = 0;
if (l == r) {
return ;
}
int mid = (l + r) >> 1;
tree[v].l = ++sz;
tree[v].r = ++sz;
build(tree[v].l, l, mid);
build(tree[v].r, mid + 1, r);
}
void upd(int nv, int ov, int pos, int l = 1, int r = n) {
tree[nv].val = tree[ov].val;
if (l == r) {
tree[nv].val++;
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
tree[nv].l = ++sz;
tree[nv].r = tree[ov].r;
upd(tree[nv].l, tree[ov].l, pos, l, mid);
} else {
tree[nv].l = tree[ov].l;
tree[nv].r = ++sz;
upd(tree[nv].r, tree[ov].r, pos, mid + 1, r);
}
tree[nv].val = tree[tree[nv].l].val + tree[tree[nv].r].val;
}
int get(int nv, int ov, int l, int r, int tl = 1, int tr = n) {
if (tl > r || tr < l) return 0;
if (l <= tl && tr <= r) return tree[nv].val - tree[ov].val;
int mid = (tl + tr) >> 1;
return get(tree[nv].l, tree[ov].l, l, r, tl, mid) + get(tree[nv].r, tree[ov].r, l, r, mid + 1, tr);
}
main() {
toint['A'] = 0;
toint['G'] = 1;
toint['C'] = 2;
toint['U'] = 3;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
cin >> s[i];
t[i] = s[i];
reverse(t[i].begin(), t[i].end());
}
sort(s + 1, s + n + 1);
sort(t + 1, t + n + 1);
for (int i = 1; i <= n; i++) {
ar[i] = add(t[i], i);
}
root[0] = 1;
sz = 0;
build();
for (int i = 1; i <= n; i++) {
root[i] = ++sz;
upd(root[i], root[i - 1], ar[i]);
}
while (m--) {
string S, T;
cin >> S >> T;
int l = lower_bound(s + 1, s + n + 1, S) - s;
S += '[';
int r = upper_bound(s + 1, s + n + 1, S) - s - 1;
if (l > r) {
puts("0");
continue;
}
reverse(T.begin(), T.end());
int L, R;
L = lower_bound(t + 1, t + n + 1, T) - t;
T += '[';
R = upper_bound(t + 1, t + n + 1, T) - t - 1;
if (L > R) {
puts("0");
continue;
}
//cout << l << ' ' << r << ' ' << L << ' ' << R << endl;
printf("%d\n", get(root[R], root[L - 1], l, r));
}
}
Compilation message
selling_rna.cpp: In function 'int add(std::__cxx11::string&, int)':
selling_rna.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < t.size(); i++) {
~~^~~~~~~~~~
selling_rna.cpp:28:30: warning: array subscript has type 'char' [-Wchar-subscripts]
if (st[cur].to[toint[t[i]]] == -1) {
^
selling_rna.cpp:29:28: warning: array subscript has type 'char' [-Wchar-subscripts]
st[cur].to[toint[t[i]]] = ++sz;
^
selling_rna.cpp:32:32: warning: array subscript has type 'char' [-Wchar-subscripts]
cur = st[cur].to[toint[t[i]]];
^
selling_rna.cpp: At global scope:
selling_rna.cpp:93:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
104544 KB |
Output is correct |
2 |
Correct |
88 ms |
104568 KB |
Output is correct |
3 |
Correct |
89 ms |
104552 KB |
Output is correct |
4 |
Correct |
89 ms |
104468 KB |
Output is correct |
5 |
Correct |
87 ms |
104444 KB |
Output is correct |
6 |
Correct |
89 ms |
104440 KB |
Output is correct |
7 |
Correct |
91 ms |
104440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
378 ms |
113276 KB |
Output is correct |
2 |
Correct |
432 ms |
113432 KB |
Output is correct |
3 |
Correct |
385 ms |
113256 KB |
Output is correct |
4 |
Correct |
396 ms |
113400 KB |
Output is correct |
5 |
Correct |
302 ms |
110132 KB |
Output is correct |
6 |
Correct |
322 ms |
110072 KB |
Output is correct |
7 |
Correct |
451 ms |
113528 KB |
Output is correct |
8 |
Correct |
518 ms |
114868 KB |
Output is correct |
9 |
Correct |
547 ms |
114856 KB |
Output is correct |
10 |
Correct |
382 ms |
112348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
356 ms |
105644 KB |
Output is correct |
2 |
Correct |
260 ms |
105208 KB |
Output is correct |
3 |
Correct |
298 ms |
105316 KB |
Output is correct |
4 |
Correct |
259 ms |
105208 KB |
Output is correct |
5 |
Correct |
249 ms |
105192 KB |
Output is correct |
6 |
Correct |
303 ms |
105308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
104544 KB |
Output is correct |
2 |
Correct |
88 ms |
104568 KB |
Output is correct |
3 |
Correct |
89 ms |
104552 KB |
Output is correct |
4 |
Correct |
89 ms |
104468 KB |
Output is correct |
5 |
Correct |
87 ms |
104444 KB |
Output is correct |
6 |
Correct |
89 ms |
104440 KB |
Output is correct |
7 |
Correct |
91 ms |
104440 KB |
Output is correct |
8 |
Correct |
378 ms |
113276 KB |
Output is correct |
9 |
Correct |
432 ms |
113432 KB |
Output is correct |
10 |
Correct |
385 ms |
113256 KB |
Output is correct |
11 |
Correct |
396 ms |
113400 KB |
Output is correct |
12 |
Correct |
302 ms |
110132 KB |
Output is correct |
13 |
Correct |
322 ms |
110072 KB |
Output is correct |
14 |
Correct |
451 ms |
113528 KB |
Output is correct |
15 |
Correct |
518 ms |
114868 KB |
Output is correct |
16 |
Correct |
547 ms |
114856 KB |
Output is correct |
17 |
Correct |
382 ms |
112348 KB |
Output is correct |
18 |
Correct |
356 ms |
105644 KB |
Output is correct |
19 |
Correct |
260 ms |
105208 KB |
Output is correct |
20 |
Correct |
298 ms |
105316 KB |
Output is correct |
21 |
Correct |
259 ms |
105208 KB |
Output is correct |
22 |
Correct |
249 ms |
105192 KB |
Output is correct |
23 |
Correct |
303 ms |
105308 KB |
Output is correct |
24 |
Correct |
502 ms |
113664 KB |
Output is correct |
25 |
Correct |
659 ms |
113904 KB |
Output is correct |
26 |
Correct |
456 ms |
113756 KB |
Output is correct |
27 |
Correct |
498 ms |
113748 KB |
Output is correct |
28 |
Correct |
1053 ms |
115980 KB |
Output is correct |
29 |
Correct |
828 ms |
109048 KB |
Output is correct |