#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD1 = 1000003013;
const int MOD2 = 1000003241;
const int BASE = 5;
int n, q;
int decode[256];
// int base1[MAXN];
// int base2[MAXN];
struct String
{
std::string value;
struct Hash
{
llong value1, value2;
Hash()
{
value1 = value2 = 0;
}
void push(char letter)
{
value1 *= BASE;
value2 *= BASE;
value1 += decode[letter];
value2 += decode[letter];
value1 %= MOD1;
value2 %= MOD2;
}
friend bool operator < (const Hash &a, const Hash &b)
{
return a.value1 < b.value1 || (a.value1 == b.value1 && a.value2 < b.value2);
}
friend bool operator == (const Hash &a, const Hash &b)
{
return a.value1 == b.value1 && a.value2 == b.value2;
}
};
std::vector <Hash> prefix;
void initalize()
{
Hash curr;
prefix.reserve(value.size());
for (int i = 0 ; i < value.size() ; ++i)
{
curr.push(value[i]);
prefix.push_back(curr);
}
}
friend bool operator < (const String &a, const String &b)
{
int l = -1, r = std::max(a.value.size(), b.value.size()), mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (a.prefix[mid] == b.prefix[mid]) l = mid;
else r = mid;
}
if (r == std::max(a.value.size(), b.value.size()))
{
return a.value.size() < b.value.size();
}
return a.value[r] < b.value[r];
}
bool isPrefix(const String &a)
{
if (a.value.size() <= value.size() && a.prefix.back() == prefix[a.value.size() - 1]) return true;
return false;
}
};
String s[MAXN];
struct Query
{
char type;
String::Hash hash;
int idx;
};
int output[MAXN];
std::vector <Query> queries[MAXN];
void solve()
{
std::sort(s + 1, s + 1 + n);
for (int i = 1 ; i <= q ; ++i)
{
// std::cout << "here: " << i << '\n' << std::flush;
String p, q;
std::cin >> p.value >> q.value;
std::reverse(q.value.begin(), q.value.end());
p.initalize(); q.initalize();
int start, end;
bool isOk = true;
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (s[mid].isPrefix(p))
{
r = mid;
continue;
}
if (s[mid] < p) l = mid;
else r = mid;
}
start = r;
isOk &= s[r].isPrefix(p);
}
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = l + r >> 1;
// std::cout << "here: " << p.value << ' ' << s[mid].value << ' ' << l << ' ' << r << ' ' << mid << ' ' << (p.value < s[mid].value) << '\n';
if (s[mid].isPrefix(p))
{
l = mid;
continue;
}
if (s[mid] < p) l = mid;
else r = mid;
}
end = l;
isOk &= s[l].isPrefix(p);
}
if (end < start || !isOk)
{
continue;
}
// std::cout << "heeeree"
assert(start == 1 || !s[start - 1].isPrefix(p));
assert(s[start].isPrefix(p));
assert(s[end].isPrefix(p));
// std::cout << "start end: " << p.value << ' ' << start << ' ' << end << '\n';
queries[start - 1].push_back({'-', q.prefix.back(), i});
queries[end].push_back({'+', q.prefix.back(), i});
}
std::unordered_map <llong, int> cnt;
for (int i = 1 ; i <= n ; ++i)
{
String::Hash curr;
for (int j = s[i].value.size() - 1 ; j >= 0 ; --j)
{
curr.push(s[i].value[j]);
cnt[curr.value1 * MOD1 + curr.value2]++;
}
for (const auto &[type, h, idx] : queries[i])
{
if (type == '-') output[idx] -= cnt[h.value1 * MOD1 + h.value2];
else output[idx] += cnt[h.value1 * MOD1 + h.value2];
}
}
}
void input()
{
std::cin >> n >> q;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> s[i].value;
s[i].initalize();
}
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << output[i] << '\n';
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
void initialize()
{
decode['A'] = 1;
decode['C'] = 2;
decode['G'] = 3;
decode['U'] = 4;
// base1[0] = base2[0] = 1;
// for (int i = 1 ; i < MAXN ; ++i)
// {
// base1[i] = (1LL * base1[i - 1] * BASE) % MOD1;
// base2[i] = (1LL * base2[i - 1] * BASE) % MOD2;
// }
}
int main()
{
initialize();
fastIOI();
input();
solve();
print();
return 0;
}
Compilation message
selling_rna.cpp: In member function 'void String::Hash::push(char)':
selling_rna.cpp:34:30: warning: array subscript has type 'char' [-Wchar-subscripts]
34 | value1 += decode[letter];
| ^~~~~~
selling_rna.cpp:35:30: warning: array subscript has type 'char' [-Wchar-subscripts]
35 | value2 += decode[letter];
| ^~~~~~
selling_rna.cpp: In member function 'void String::initalize()':
selling_rna.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0 ; i < value.size() ; ++i)
| ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool operator<(const String&, const String&)':
selling_rna.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | mid = l + r >> 1;
| ~~^~~
selling_rna.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
73 | if (r == std::max(a.value.size(), b.value.size()))
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:116:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
116 | mid = l + r >> 1;
| ~~^~~
selling_rna.cpp:135:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8788 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
905 ms |
130572 KB |
Output is correct |
| 2 |
Correct |
898 ms |
127448 KB |
Output is correct |
| 3 |
Correct |
85 ms |
46304 KB |
Output is correct |
| 4 |
Correct |
88 ms |
46416 KB |
Output is correct |
| 5 |
Incorrect |
531 ms |
81388 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
14896 KB |
Output is correct |
| 2 |
Correct |
30 ms |
14020 KB |
Output is correct |
| 3 |
Correct |
41 ms |
14784 KB |
Output is correct |
| 4 |
Correct |
30 ms |
13572 KB |
Output is correct |
| 5 |
Correct |
35 ms |
13656 KB |
Output is correct |
| 6 |
Correct |
42 ms |
14272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8788 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8536 KB |
Output is correct |
| 8 |
Correct |
905 ms |
130572 KB |
Output is correct |
| 9 |
Correct |
898 ms |
127448 KB |
Output is correct |
| 10 |
Correct |
85 ms |
46304 KB |
Output is correct |
| 11 |
Correct |
88 ms |
46416 KB |
Output is correct |
| 12 |
Incorrect |
531 ms |
81388 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
