#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
struct Fenwick {
vector <int> aib;
int n;
inline void init(int _n) {
n = _n;
aib.resize(n + 1);
}
inline void update(int pos, int val) {
for(int i = pos; i <= n; i += lsb(i)) {
aib[i] += val;
}
}
inline int query(int pos) {
int ans = 0;
for(int i = pos; i > 0; i -= lsb(i)) {
ans += aib[i];
}
return ans;
}
};
struct Trie {
Trie *son[26];
int sz;
vector <int> pos;
Trie() {
memset(son, NULL, sizeof(son));
sz = 0;
}
};
Trie *root1 = new Trie;
Trie *root2 = new Trie;
void add(Trie *nod, string &str, int p, int id) {
if(p == str.size()) {
nod -> sz++;
nod -> pos.push_back(id);
}
else {
int ch = str[p] - 'A';
if(nod -> son[ch] == NULL) {
nod -> son[ch] = new Trie;
}
add(nod -> son[ch], str, p + 1, id);
nod -> sz++;
}
}
void dfs(Trie *nod, string &str, int &id) {
reverse(str.begin(), str.end());
for(auto it : nod -> pos) {
add(root2, str, 0, ++id);
}
reverse(str.begin(), str.end());
for(int ch = 0; ch < 26; ch++) {
if(nod -> son[ch] != NULL) {
str.push_back(ch + 'A');
dfs(nod -> son[ch], str, id);
str.pop_back();
}
}
}
void query(Trie *nod, string &str, int p, pair <int, int> &cur) {
if(nod == NULL) {
cur = {2, 1};
return ;
}
if(p == str.size()) {
cur.second = cur.first + nod -> sz;
cur.first++;
}
else {
int ch = str[p] - 'A';
for(int i = 0; i < ch; i++) {
if(nod -> son[i] != NULL) {
cur.first += nod -> son[i] -> sz;
}
}
cur.first += nod -> pos.size();
query(nod -> son[ch], str, p + 1, cur);
}
}
void dfs1(Trie *nod, vector <int> &arr) {
for(auto it : nod -> pos) {
arr.push_back(it);
}
for(int ch = 0; ch < 26; ch++) {
if(nod -> son[ch] != NULL) {
dfs1(nod -> son[ch], arr);
}
}
}
struct Query {
int pos, val;
char sign;
int id;
bool operator <(const Query &other) const {
return pos < other.pos;
}
};
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, m;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(i = 1; i <= n; i++) {
string str;
cin >> str;
add(root1, str, 0, i);
}
string str;
int id = 0;
dfs(root1, str, id);
vector <int> arr(1);
dfs1(root2, arr);
vector <Query> qry;
for(i = 1; i <= m; i++) {
string a, b;
cin >> a >> b;
reverse(b.begin(), b.end());
pair <int, int> cur1, cur2;
cur1 = cur2 = {0, 0};
query(root1, a, 0, cur1);
query(root2, b, 0, cur2);
if(cur1.first <= cur1.second && cur2.first <= cur2.second) {
qry.push_back({cur2.first - 1, cur1.first - 1, 1, i});
qry.push_back({cur2.first - 1, cur1.second, -1, i});
qry.push_back({cur2.second, cur1.first - 1, -1, i});
qry.push_back({cur2.second, cur1.second, 1, i});
}
//cerr << cur1.first << " " << cur1.second << " " << cur2.first << " " << cur2.second << "\n";
}
Fenwick fen; fen.init(n);
sort(qry.begin(), qry.end());
vector <int> sol(m + 1);
int pos = 0, sz = qry.size();
for(i = 0; i <= n; i++) {
if(i > 0) {
fen.update(arr[i], 1);
}
while(pos < sz && qry[pos].pos <= i) {
sol[qry[pos].id] += qry[pos].sign * fen.query(qry[pos].val);
pos++;
}
}
for(i = 1; i <= m; i++) {
cout << sol[i] << "\n";
}
//cin.close();
//cout.close();
return 0;
}
/*void print(Trie *nod) {
for(auto it : nod -> pos) {
cerr << it << " ";
}
cerr << "\n";
for(int ch = 0; ch < 26; ch++) {
if(nod -> son[ch] != NULL) {
print(nod -> son[ch]);
}
}
}*/
Compilation message
selling_rna.cpp: In constructor 'Trie::Trie()':
selling_rna.cpp:38:38: warning: passing NULL to non-pointer argument 2 of 'void* memset(void*, int, size_t)' [-Wconversion-null]
memset(son, NULL, sizeof(son));
^
selling_rna.cpp: In function 'void add(Trie*, std::__cxx11::string&, int, int)':
selling_rna.cpp:48:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p == str.size()) {
~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(Trie*, std::__cxx11::string&, int&)':
selling_rna.cpp:64:14: warning: unused variable 'it' [-Wunused-variable]
for(auto it : nod -> pos) {
^~
selling_rna.cpp: In function 'void query(Trie*, std::__cxx11::string&, int, std::pair<int, int>&)':
selling_rna.cpp:84:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p == str.size()) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
750 ms |
495068 KB |
Output is correct |
| 2 |
Correct |
660 ms |
472580 KB |
Output is correct |
| 3 |
Execution timed out |
1583 ms |
489576 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
5352 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4512 KB |
Output is correct |
| 3 |
Correct |
40 ms |
6280 KB |
Output is correct |
| 4 |
Correct |
27 ms |
5512 KB |
Output is correct |
| 5 |
Correct |
29 ms |
4764 KB |
Output is correct |
| 6 |
Correct |
31 ms |
6256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Correct |
750 ms |
495068 KB |
Output is correct |
| 9 |
Correct |
660 ms |
472580 KB |
Output is correct |
| 10 |
Execution timed out |
1583 ms |
489576 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
