#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define lb(s, a) lower_bound(all(s), (a)) - s.begin()
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int ar = 2e6+5;
const ll mod = 1e9+7;
const int oo = 1e9;
int n, m, maxx = 0, maxy = 0;
int cs(char a) {
if(a == 'C') return 0;
if(a == 'U') return 1;
if(a == 'G') return 2;
return 3;
}
struct Trie {
struct Node{
int child[5];
} nodes[ar];
int cur;
Trie() : cur(0) {
memset(nodes[0].child, -1, sizeof(nodes[cur].child));
};
int new_node() {
cur++;
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
return cur;
}
void add(string s) {
int pos = 0;
for (auto f : s) {
int c = cs(f);
if (nodes[pos].child[c] == -1) {
nodes[pos].child[c] = new_node();
}
pos = nodes[pos].child[c];
}
}
vector <int> trace(string s) {
int pos = 0;
vector <int> res;
for (auto f : s) {
int c = cs(f);
if (nodes[pos].child[c] == -1) {
nodes[pos].child[c] = new_node();
}
pos = nodes[pos].child[c];
res.push_back(in[pos]);
}
return res;
}
int in[ar], out[ar], timeDfs = 0;
void dfs(int u) {
in[u] = ++timeDfs;
for(int i = 0; i < 4; ++i) if(nodes[u].child[i] != -1)
dfs(nodes[u].child[i]);
out[u] = timeDfs;
}
ii get(string s) {
int pos = 0;
for (auto f : s) {
int c = cs(f);
if (nodes[pos].child[c] == -1)
return {-1, -1};
pos = nodes[pos].child[c];
}
return {in[pos], out[pos]};
}
} t1, t2;
int bit[ar], res[ar], L[ar];
vector <int> x[ar];
struct Query {
int l, r, i;
bool t;
};
vector <Query> query[ar];
string s[100005];
void update(int i, int val) {
for(; i <= maxy; i += i & -i)
bit[i] += val;
}
int get(int i) {
if(i == 0) return 0;
int res = 0;
for(; i > 0; i -= i & -i)
res += bit[i];
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "b"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> s[i];
t1.add(s[i]);
string tmp = s[i];
reverse(all(tmp));
t2.add(tmp);
}
t1.dfs(0);
t2.dfs(0);
for(int i = 1; i <= n; ++i) {
string tmp = s[i];
reverse(all(tmp));
vector <int> tmp1 = t1.trace(s[i]), tmp2 = t2.trace(tmp);
reverse(all(tmp2));
for(int j = 0; j < tmp1.size(); ++j) {
x[tmp1[j]].push_back(tmp2[j]);
}
}
string p, q;
for(int i = 1; i <= m; ++i) {
cin >> p >> q;
ii p1 = t1.get(p);
if(p1.fi == -1) continue;
reverse(all(q));
ii p2 = t2.get(q);
if(p2.fi == -1) continue;
if(p1.fi > p2.fi) swap(p1.fi, p2.fi);
if(p1.se > p2.se) swap(p2.se, p1.se);
// cout << i << ' ' << p1.fi << ' ' << p1.se << ' ' << p2.fi << ' ' << p2.se << '\n';
query[p1.fi - 1].push_back({p1.se, p2.se, i, 0});
query[p2.fi].push_back({p1.se, p2.se, i, 1});
maxx = max({maxx, p1.fi, p2.fi});
maxy = max({maxy, p1.se, p2.se});
}
for(int i = 1; i <= maxx; ++i) {
for(auto y : x[i])
update(y, 1);
for(auto [l, r, j, t] : query[i]) {
int tmp = get(r) - get(l - 1);
if(t == 0) L[j] = tmp;
else res[j] = tmp - L[j];
}
}
for(int i = 1; i <= m; ++i)
cout << res[i] << '\n';
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int j = 0; j < tmp1.size(); ++j) {
| ~~^~~~~~~~~~~~~
selling_rna.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
113500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
183888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
117792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
113500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
