#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();
}
if (a.value[r] < b.value[r]) return true;
return false;
}
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);
return;
for (int i = 1 ; i <= q ; ++i)
{
String p, q;
std::cin >> p.value >> q.value;
std::reverse(q.value.begin(), q.value.end());
p.initalize(); q.initalize();
int start, end;
{
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;
}
{
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;
}
// 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::map <String::Hash, 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]++;
}
for (const auto &[type, h, idx] : queries[i])
{
if (type == '-') output[idx] -= cnt[h];
else output[idx] += cnt[h];
}
}
}
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:33:30: warning: array subscript has type 'char' [-Wchar-subscripts]
33 | value1 += decode[letter];
| ^~~~~~
selling_rna.cpp: In member function 'void String::initalize()':
selling_rna.cpp:55:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0 ; i < value.size() ; ++i)
| ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool operator<(const String&, const String&)':
selling_rna.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | mid = l + r >> 1;
| ~~^~~
selling_rna.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
72 | 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:134:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
134 | mid = l + r >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
8284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
36 ms |
41816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
8284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
