#include <bits/stdc++.h>
using namespace std;
#define task "test"
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define vii vector <ii>
#define vi vector <int>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
void solve();
int32_t main() {
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
int tc = 1; // cin >> tc;
FOR(i, 1, tc) {
solve();
}
}
const int N = 1e5+5;
int n, m, trch[200], queryAns[N];
pair <string, int> s[N];
vector <ii> query[N];
struct fenwickTree {
int f[N*20];
void upd(int id, int val) {
for(; id<N*20; id+=id&-id) f[id]+=val;
}
int get(int id) {
int res=0;
for(; id>0; id-=id&-id) res+=f[id];
return res;
}
int getRange(int L, int R) {
return get(R) - get(L-1);
}
} fwt;
// build prefix trie
int Time, st[N*20], en[N*20];
struct preNode {
int cnt = 0, child[4];
preNode () {
fill(begin(child), end(child), -1);
}
};
vector <preNode> preTrie(1);
int pre_add_string(const string &newString) {
int cur = 0;
for(char c:newString) {
int nxtCh = trch[(int)c];
if(preTrie[cur].child[nxtCh] == -1) {
preTrie[cur].child[nxtCh] = sz(preTrie);
preTrie.eb();
}
cur = preTrie[cur].child[nxtCh];
// cout<<cur<<'\n';
}
preTrie[cur].cnt++;
return cur;
}
void pre_trie_dfs(int u) {
st[u] = ++Time;
// cout<<u<<" "<<st[u]<<'\n';
FOR(i, 0, 3) {
if(preTrie[u].child[i] != -1) {
pre_trie_dfs(preTrie[u].child[i]);
}
}
en[u] = Time;
}
int pre_get_string(const string &f) {
int cur = 0;
for(char c:f) {
int nxtCh = trch[(int)c];
if(preTrie[cur].child[nxtCh] == -1) {
preTrie[cur].child[nxtCh] = sz(preTrie);
preTrie.eb();
}
cur = preTrie[cur].child[nxtCh];
}
return cur;
}
// build suffix trie
int sub[N*20], suf_st[N*20], suf_en[N*20], tour[N*20];
struct sufNode {
int cnt = 0, id = -1, child[4];
sufNode () {
fill(begin(child), end(child), -1);
}
};
vector <sufNode> sufTrie(1);
void suf_add_string(const string &newString, int tour_pos) {
int cur = 0;
for(char c:newString) {
int nxtCh = trch[(int)c];
if(sufTrie[cur].child[nxtCh] == -1) {
sufTrie[cur].child[nxtCh] = sz(sufTrie);
sufTrie.eb();
}
cur = sufTrie[cur].child[nxtCh];
}
sufTrie[cur].cnt++;
sufTrie[cur].id = tour_pos;
}
int suf_get_string(const string &f) {
int cur = 0;
for(char c:f) {
int nxtCh = trch[(int)c];
if(sufTrie[cur].child[nxtCh] == -1) {
sufTrie[cur].child[nxtCh] = sz(sufTrie);
sufTrie.eb();
}
cur = sufTrie[cur].child[nxtCh];
}
return cur;
}
void suf_get_size(int u) {
suf_st[u] = ++Time;
sub[u] = 1;
FOR(i, 0, 3) {
if(sufTrie[u].child[i] != -1) {
suf_get_size(sufTrie[u].child[i]);
sub[u] += sub[sufTrie[u].child[i]];
}
}
suf_en[u] = Time;
}
void suf_dfs_ans(int u) {
int bigCh = -1;
FOR(i, 0, 3) if(sufTrie[u].child[i] != -1) {
if(bigCh == -1 || sub[bigCh] < sub[sufTrie[u].child[i]]) {
bigCh = sufTrie[u].child[i];
}
}
FOR(i, 0, 3) if(sufTrie[u].child[i] != -1 && sufTrie[u].child[i] != bigCh) {
suf_dfs_ans(sufTrie[u].child[i]);
FOR(j, suf_st[sufTrie[u].child[i]], suf_en[sufTrie[u].child[i]]) {
if(sufTrie[tour[j]].id != -1) {
fwt.upd(sufTrie[tour[j]].id, -sufTrie[tour[j]].cnt);
}
}
/// delete from fenwick tree
}
if(bigCh != -1) suf_dfs_ans(bigCh);
FOR(i, 0, 3) if(sufTrie[u].child[i] != -1 && sufTrie[u].child[i] != bigCh) {
FOR(j, suf_st[sufTrie[u].child[i]], suf_en[sufTrie[u].child[i]]) {
if(sufTrie[tour[j]].id != -1) {
fwt.upd(sufTrie[tour[j]].id, sufTrie[tour[j]].cnt);
}
}
/// add to fenwick tree
}
if(sufTrie[u].id != -1) fwt.upd(sufTrie[u].id, sufTrie[u].cnt);
/// add u to fenwick tree
for(auto [preN, id]:query[u]) {
queryAns[id] = fwt.getRange(st[preN], en[preN]);
}
}
void solve() {
cin >> n >> m;
trch['C'] = 0, trch['U'] = 1, trch['G'] = 2, trch['A'] = 3;
FOR(i, 1, n) {
cin >> s[i].fi;
s[i].se = pre_add_string(s[i].fi);
reverse(all(s[i].fi));
suf_add_string(s[i].fi, s[i].se);
}
FOR(i, 1, m) {
string pre, suf; cin >> pre >> suf;
reverse(all(suf));
int idp = pre_get_string(pre),
ids = suf_get_string(suf);
query[ids].eb(idp, i);
}
pre_trie_dfs(0);
suf_get_size(0);
suf_dfs_ans(0);
FOR(i, 1, m) {
cout << queryAns[i] << '\n';
}
}
Compilation message
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
124084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
23640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
