#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10, alphabet = 26;
int n, m;
string rna[maxn];
struct query
{
string p, q;
}ask[maxn];
void input()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> rna[i];
for (int i = 1; i <= m; i ++)
cin >> ask[i].p >> ask[i].q;
sort(rna + 1, rna + n + 1);
}
struct trie
{
trie *child[alphabet];
int left, right;
vector < int > bucket;
trie()
{
for (int i = 0; i < alphabet; i ++)
child[i] = NULL;
left = 1e9;
right = 0;
}
};
void add(trie *root, string &word, int pos, int idx)
{
root -> left = min(root -> left, idx);
root -> right = max(root -> right, idx);
root -> bucket.push_back(idx);
if (pos == word.size())
return;
int go = word[pos] - 'A';
if (root -> child[go] == NULL)
root -> child[go] = new trie();
add(root -> child[go], word, pos + 1, idx);
}
trie *ft = new trie(), *bk = new trie();
void build_trie()
{
for (int i = 1; i <= n; i ++)
{
add(ft, rna[i], 0, i);
reverse(rna[i].begin(), rna[i].end());
add(bk, rna[i], 0, i);
}
}
pair < int, int > query_range(trie *root, string &word, int pos)
{
if (pos == word.size())
return make_pair(root -> left, root -> right);
int go = word[pos] - 'A';
if (root -> child[go] == NULL)
return make_pair(1e9, 0);
return query_range(root -> child[go], word, pos + 1);
}
int calculate(vector < int > &bucket, pair < int, int > range)
{
int lf = 0, rf = (int)(bucket.size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (bucket[mf] < range.first)
lf = mf + 1;
else
rf = mf - 1;
}
int f1 = lf;
lf = 0;
rf = (int)(bucket.size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (bucket[mf] <= range.second)
lf = mf + 1;
else
rf = mf - 1;
}
int f2 = rf;
return max(0, f2 - f1 + 1);
}
int query(trie *root, string &word, int pos, pair < int, int > &range)
{
if (pos == word.size())
{
return calculate(root -> bucket, range);
}
int go = word[pos] - 'A';
if (root -> child[go] == NULL)
return 0;
return query(root -> child[go], word, pos + 1, range);
}
void solve_queries()
{
for (int i = 1; i <= m; i ++)
{
pair < int, int > range = query_range(ft, ask[i].p, 0);
int ans = query(bk, ask[i].q, 0, range);
cout << ans << endl;
}
}
void solve()
{
input();
build_trie();
solve_queries();
}
int main()
{
solve();
return 0;
}
Compilation message
selling_rna.cpp: In function 'void add(trie*, std::string&, int, int)':
selling_rna.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> query_range(trie*, std::string&, int)':
selling_rna.cpp:78:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(trie*, std::string&, int, std::pair<int, int>&)':
selling_rna.cpp:120:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
536 ms |
584552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
11812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
