#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 4> A;
const int MXN = 100005, MXM = 2000005;
int n, m;
string s[MXN], p[MXN], q[MXN];
int ans[MXN];
vector<pii> v;
int M[200];
namespace TRIE {
int nc, cnt[MXM];
A chd[MXM];
int new_node() {
cnt[nc] = 0;
FOR(i, 0, 4) chd[nc][i] = 0;
return nc++;
}
void init() {
nc = 2;
}
void PUSH(string &s) {
int now = 1;
for (auto &i : s) {
int id = M[i];
if (chd[now][id] == 0) chd[now][id] = new_node();
now = chd[now][id];
cnt[now]++;
}
}
int QUERY(string &s) {
int now = 1;
for (auto &i : s) {
int id = M[i];
now = chd[now][id];
}
debug(s, now, cnt[now]);
return cnt[now];
}
}
void miku() {
M['A'] = 0;
M['U'] = 1;
M['C'] = 2;
M['G'] = 3;
cin >> n >> m;
FOR(i, 0, n) cin >> s[i];
sort(s, s + n);
FOR(i, 1, m + 1) {
cin >> p[i] >> q[i];
reverse(q[i].begin(), q[i].end());
v.push_back(mp((int) (lower_bound(s, s + n, p[i]) - s), -i));
p[i].back()++;
v.push_back(mp((int) (lower_bound(s, s + n, p[i]) - s), i));
}
FOR(i, 0, n) v.push_back(mp(i, 0LL));
sort(v.begin(), v.end(), [](pii a, pii b) -> bool {
if (a.fs != b.fs) return a.fs < b.fs;
if (a.sc == 0) return false;
if (b.sc == 0) return true;
return a.fs < b.fs;
});
FOR(i, 0, n) cout << s[i] << '\n';
TRIE::init();
for (auto [x, type] : v) {
// debug(x, type);
if (type == 0) {
reverse(s[x].begin(), s[x].end());
debug("PUSH", s[x]);
TRIE::PUSH(s[x]);
continue;
}
if (type > 0) ans[type] += TRIE::QUERY(q[type]);
else ans[-type] -= TRIE::QUERY(q[-type]);
}
FOR(i, 1, m + 1) cout << ans[i] << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
selling_rna.cpp: In function 'void TRIE::PUSH(std::string&)':
selling_rna.cpp:46:24: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | int id = M[i];
| ^
selling_rna.cpp: In function 'int TRIE::QUERY(std::string&)':
selling_rna.cpp:56:24: warning: array subscript has type 'char' [-Wchar-subscripts]
56 | int id = M[i];
| ^
selling_rna.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
selling_rna.cpp:59:9: note: in expansion of macro 'debug'
59 | debug(s, now, cnt[now]);
| ^~~~~
selling_rna.cpp: In function 'void miku()':
selling_rna.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
selling_rna.cpp:92:13: note: in expansion of macro 'debug'
92 | debug("PUSH", s[x]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
55228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
14296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
