#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define dbg(x) cerr << #x << " is " << x << "\n";
using ll = long long;
using ii = pair<ll,ll>;
const int N = 5e5+10;
const int M = 1e6+10;
int n, m;
char s[N];
char ID(char x) {
if(x == 'A') return 'a';
if(x == 'C') return 'b';
if(x == 'G') return 'c';
return 'd';
}
struct Trie{
int node, to[4][M];
vector<int> ending[M];
Trie() { node = 1; }
void insert(int len, int id) {
int cur = 1;
for(int i = 0; i < len; i++) {
int val = ID(s[i]) - 'a';
if(to[val][cur] == 0) to[val][cur] = ++node;
cur = to[val][cur];
}
ending[cur].push_back(id);
}
int in[M], out[M];
vector<int> eul;
void dfs(int u) {
in[u] = eul.size();
for(int x : ending[u]) eul.push_back(x);
for(int v = 0; v < 4; v++) if(to[v][u] != 0)
dfs(to[v][u]);
out[u] = eul.size() - 1;
}
void find(int &l, int &r) {
int cur = 1, len = strlen(s);
for(int i = 0; i < len; i++) {
int val = ID(s[i]) - 'a';
if(to[val][cur] == 0) {
l = r = -1;
return;
} cur = to[val][cur];
}
l = in[cur], r = out[cur];
}
}trie, eirt;
int result[N];
struct CPR{
struct data{
int x, y1, y2;
int ty, id;
// point = 0, [ = -1, ] = 1
bool operator<(data o) const {
if(x == o.x) return ty < o.ty;
return x < o.x;
}
};
vector<data> v;
void insert_point(int x, int y) {
x++, y++;
v.push_back({x, y, 0, 0, 0});
}
void insert_rect(int x1, int x2, int y1, int y2, int id) {
x1++, y1++, x2++, y2++;
v.push_back({x1, y1, y2, -1, id});
v.push_back({x2, y1, y2, +1, id});
}
int bit[N];
void upd(int pos, int x) {
while(pos < N) bit[pos] += x, pos += pos&-pos;
}
int get(int pos, int r = 0) {
while(pos > 0) r += bit[pos], pos -= pos&-pos;
return r;
}
void sweep() {
sort(all(v));
for(auto d : v) {
if(d.ty == 0) upd(d.y1, +1);
else result[d.id] += d.ty * (get(d.y2) - get(d.y1 - 1));
}
}
}ds;
int mp[N];
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) {
scanf(" %s", s);
int len = strlen(s);
trie.insert(len, i);
reverse(s, s + len);
eirt.insert(len, i);
}
trie.dfs(1); eirt.dfs(1);
for(int i = 0; i < n; i++) mp[trie.eul[i]] = i;
for(int i = 0; i < n; i++) {
eirt.eul[i] = mp[eirt.eul[i]];
ds.insert_point(i, eirt.eul[i]);
}
for(int i = 0; i < m; i++) {
scanf(" %s", s);
int l, r; trie.find(l, r);
scanf(" %s", s);
reverse(s, s + strlen(s));
int L, R; eirt.find(L, R);
if(l != -1 && L != -1 && l <= r && L <= R) ds.insert_rect(L, R, l, r, i);
}
ds.sweep();
for(int i = 0; i < m; i++)
printf("%d\n", result[i]);
return 0;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
110 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
112 | scanf(" %s", s);
| ~~~~~^~~~~~~~~~
selling_rna.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf(" %s", s);
| ~~~~~^~~~~~~~~~
selling_rna.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf(" %s", s);
| ~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
47488 KB |
Output is correct |
2 |
Correct |
32 ms |
47480 KB |
Output is correct |
3 |
Correct |
32 ms |
47480 KB |
Output is correct |
4 |
Correct |
33 ms |
47480 KB |
Output is correct |
5 |
Correct |
34 ms |
47488 KB |
Output is correct |
6 |
Correct |
32 ms |
47488 KB |
Output is correct |
7 |
Correct |
34 ms |
47480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
156 ms |
128504 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
53704 KB |
Output is correct |
2 |
Correct |
61 ms |
50944 KB |
Output is correct |
3 |
Correct |
70 ms |
51364 KB |
Output is correct |
4 |
Correct |
63 ms |
50856 KB |
Output is correct |
5 |
Correct |
70 ms |
50956 KB |
Output is correct |
6 |
Correct |
68 ms |
51396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
47488 KB |
Output is correct |
2 |
Correct |
32 ms |
47480 KB |
Output is correct |
3 |
Correct |
32 ms |
47480 KB |
Output is correct |
4 |
Correct |
33 ms |
47480 KB |
Output is correct |
5 |
Correct |
34 ms |
47488 KB |
Output is correct |
6 |
Correct |
32 ms |
47488 KB |
Output is correct |
7 |
Correct |
34 ms |
47480 KB |
Output is correct |
8 |
Runtime error |
156 ms |
128504 KB |
Execution killed with signal 11 |
9 |
Halted |
0 ms |
0 KB |
- |