#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
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) {
int num = 0;
for(int ch = 0; ch < 26; ch++) {
if(nod -> son[ch] != NULL) {
num++;
str.push_back(ch + 'A');
dfs(nod -> son[ch], str, id);
str.pop_back();
}
}
if(num == 0) {
reverse(str.begin(), str.end());
add(root2, str, 0, ++id);
reverse(str.begin(), str.end());
}
}
void query(Trie *nod, string &str, int p, pair <int, int> &cur) {
if(nod == NULL) {
cur = {-1, -1};
return ;
}
if(p == str.size()) {
cur.second = cur.first + nod -> sz;
cur.first++;
}
else {
char ch = str[p] - 'A';
for(int i = 0; i < ch; i++) {
if(nod -> son[i] != NULL) {
cur.first += nod -> son[i] -> sz;
}
}
query(nod -> son[ch], str, p + 1, cur);
}
}
void dfs1(Trie *nod, vector <int> &arr) {
int num = 0;
for(int ch = 0; ch < 26; ch++) {
if(nod -> son[ch] != NULL) {
num++;
dfs1(nod -> son[ch], arr);
}
}
if(num == 0) {
for(auto it : nod -> pos) {
arr.push_back(it);
}
}
}
struct Query {
int pos, val;
char sign;
int id;
bool operator <(const Query &other) const {
return pos < other.pos;
}
};
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;
}
inline int sum(int l, int r) {
return query(r) - query(l - 1);
}
};
/*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]);
}
}
}*/
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;
pair <int, int> cur1, cur2;
cur1 = cur2 = {0, 0};
query(root1, a, 0, cur1);
query(root2, b, 0, cur2);
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});
}
/*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;
}
Compilation message
selling_rna.cpp: In constructor 'Trie::Trie()':
selling_rna.cpp:17: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:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p == str.size()) {
~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void query(Trie*, std::__cxx11::string&, int, std::pair<int, int>&)':
selling_rna.cpp:65:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p == str.size()) {
~~^~~~~~~~~~~~~
selling_rna.cpp:76:28: warning: array subscript has type 'char' [-Wchar-subscripts]
query(nod -> son[ch], str, p + 1, cur);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
588 ms |
424936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
4916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
