#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
struct node {
node * nxt[4] = {};
int s, e;
node () {}
};
int n, m;
string s[100001];
node * trie1, * trie2;
struct _qs {
int i;
string p, q;
void scan(int idx) {
i = idx;
cin >> p >> q;
reverse(q.begin(), q.end());
}
} qis[100001];
int idx[256];
node * makeTrie(node * x, int i, string &s) {
if (i == s.length()) return x;
if (x->nxt[idx[s[i]]] == 0) x->nxt[idx[s[i]]] = new node();
return makeTrie(x->nxt[idx[s[i]]], i + 1, s);
}
int ord;
void dfsTrie(node * x) {
x->s = ++ord;
for (int i = 0; i < 4; ++i) {
if (x->nxt[i]) dfsTrie(x->nxt[i]);
}
x->e = ord;
}
node * snode1[100001];
node * snode2[100001];
node * qnode1[100001];
node * qnode2[100001];
const int mx = 2e6;
int seg[mx + 1];
pii ss[100000];
pii qs[200000];
int ans[100001];
void update(int i) {
while (i <= mx) {
++seg[i];
i += i & -i;
}
}
int query(int i) {
int ret = 0;
while (i) {
ret += seg[i];
i -= i & -i;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
idx['A'] = 0;
idx['U'] = 1;
idx['G'] = 2;
idx['C'] = 3;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
for (int i = 1; i <= m; ++i) {
qis[i].scan(i);
}
trie1 = new node();
trie2 = new node();
for (int i = 1; i <= n; ++i) {
snode1[i] = makeTrie(trie1, 0, s[i]);
reverse(s[i].begin(), s[i].end());
snode2[i] = makeTrie(trie2, 0, s[i]);
}
for (int i = 1; i <= m; ++i) {
qnode1[i] = makeTrie(trie1, 0, qis[i].p);
qnode2[i] = makeTrie(trie2, 0, qis[i].q);
}
int sz1, sz2;
ord = 0;
dfsTrie(trie1);
sz1 = ord;
ord = 0;
dfsTrie(trie2);
sz2 = ord;
for (int i = 1; i <= n; ++i) {
ss[i - 1] = pii(snode1[i]->s, snode2[i]->s);
}
sort(ss, ss + n);
for (int i = 1; i <= m; ++i) {
qs[(i - 1) << 1] = pii(qnode1[i]->s - 1, -i);
qs[(i - 1) << 1 | 1] = pii(qnode1[i]->e, i);
}
sort(qs, qs + (m << 1));
for (int i = 0, j = 0; i < (m << 1); ++i) {
while (j < n && ss[j].first <= qs[i].first) {
update(ss[j++].second);
}
int t = qs[i].second;
if (t < 0) {
t = -t;
ans[t] -= query(qnode2[t]->e) - query(qnode2[t]->s - 1);
}
else {
ans[t] += query(qnode2[t]->e) - query(qnode2[t]->s - 1);
}
}
for (int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
selling_rna.cpp: In function 'node* makeTrie(node*, int, std::__cxx11::string&)':
selling_rna.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == s.length()) return x;
~~^~~~~~~~~~~~~
selling_rna.cpp:44:24: warning: array subscript has type 'char' [-Wchar-subscripts]
if (x->nxt[idx[s[i]]] == 0) x->nxt[idx[s[i]]] = new node();
^
selling_rna.cpp:44:48: warning: array subscript has type 'char' [-Wchar-subscripts]
if (x->nxt[idx[s[i]]] == 0) x->nxt[idx[s[i]]] = new node();
^
selling_rna.cpp:45:36: warning: array subscript has type 'char' [-Wchar-subscripts]
return makeTrie(x->nxt[idx[s[i]]], i + 1, s);
^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:110:9: warning: variable 'sz1' set but not used [-Wunused-but-set-variable]
int sz1, sz2;
^~~
selling_rna.cpp:110:14: warning: variable 'sz2' set but not used [-Wunused-but-set-variable]
int sz1, sz2;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
10616 KB |
Output is correct |
2 |
Correct |
13 ms |
10768 KB |
Output is correct |
3 |
Correct |
14 ms |
10768 KB |
Output is correct |
4 |
Correct |
9 ms |
10844 KB |
Output is correct |
5 |
Correct |
12 ms |
10884 KB |
Output is correct |
6 |
Correct |
14 ms |
10884 KB |
Output is correct |
7 |
Correct |
14 ms |
10884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
200 ms |
114524 KB |
Output is correct |
2 |
Correct |
193 ms |
114524 KB |
Output is correct |
3 |
Correct |
207 ms |
114524 KB |
Output is correct |
4 |
Correct |
231 ms |
114524 KB |
Output is correct |
5 |
Correct |
323 ms |
132864 KB |
Output is correct |
6 |
Correct |
293 ms |
134764 KB |
Output is correct |
7 |
Correct |
63 ms |
134764 KB |
Output is correct |
8 |
Correct |
248 ms |
134764 KB |
Output is correct |
9 |
Correct |
175 ms |
134764 KB |
Output is correct |
10 |
Correct |
144 ms |
134764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
134764 KB |
Output is correct |
2 |
Correct |
51 ms |
134764 KB |
Output is correct |
3 |
Correct |
51 ms |
134764 KB |
Output is correct |
4 |
Correct |
47 ms |
134764 KB |
Output is correct |
5 |
Correct |
48 ms |
134764 KB |
Output is correct |
6 |
Correct |
52 ms |
134764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
10616 KB |
Output is correct |
2 |
Correct |
13 ms |
10768 KB |
Output is correct |
3 |
Correct |
14 ms |
10768 KB |
Output is correct |
4 |
Correct |
9 ms |
10844 KB |
Output is correct |
5 |
Correct |
12 ms |
10884 KB |
Output is correct |
6 |
Correct |
14 ms |
10884 KB |
Output is correct |
7 |
Correct |
14 ms |
10884 KB |
Output is correct |
8 |
Correct |
200 ms |
114524 KB |
Output is correct |
9 |
Correct |
193 ms |
114524 KB |
Output is correct |
10 |
Correct |
207 ms |
114524 KB |
Output is correct |
11 |
Correct |
231 ms |
114524 KB |
Output is correct |
12 |
Correct |
323 ms |
132864 KB |
Output is correct |
13 |
Correct |
293 ms |
134764 KB |
Output is correct |
14 |
Correct |
63 ms |
134764 KB |
Output is correct |
15 |
Correct |
248 ms |
134764 KB |
Output is correct |
16 |
Correct |
175 ms |
134764 KB |
Output is correct |
17 |
Correct |
144 ms |
134764 KB |
Output is correct |
18 |
Correct |
59 ms |
134764 KB |
Output is correct |
19 |
Correct |
51 ms |
134764 KB |
Output is correct |
20 |
Correct |
51 ms |
134764 KB |
Output is correct |
21 |
Correct |
47 ms |
134764 KB |
Output is correct |
22 |
Correct |
48 ms |
134764 KB |
Output is correct |
23 |
Correct |
52 ms |
134764 KB |
Output is correct |
24 |
Correct |
261 ms |
134764 KB |
Output is correct |
25 |
Correct |
273 ms |
134764 KB |
Output is correct |
26 |
Correct |
234 ms |
134764 KB |
Output is correct |
27 |
Correct |
266 ms |
134764 KB |
Output is correct |
28 |
Correct |
225 ms |
134764 KB |
Output is correct |
29 |
Correct |
97 ms |
134764 KB |
Output is correct |