#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
string s[200005];
unordered_map<int, int> t[400005];
long long int a[100005], p[400005], mod = 1e9 + 7;
void update(int v, int tl, int tr, int x, int y) {
if (tl == tr) {
t[v][y]++;
return;
}
int mid = (tl + tr) / 2;
if (mid >= x) update(v * 2, tl, mid, x, y);
else update(v * 2 + 1, mid + 1, tr, x, y);
t[v][y]++;
}
int sum(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return 0;
if (tl == l && tr == r) {
return t[v][x];
}
int mid = (tl + tr) / 2;
return sum(v * 2, tl, mid, l, min(r, mid), x) + sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
}
bool check(int x, string t) {
for (int i = 1; i < min(t.size(), s[x].size()); i++) {
if (s[x][i] > t[i]) return true;
if (s[x][i] < t[i]) return false;
}
return true;
}
bool check2(int x, string t) {
for (int i = 1; i < min(t.size(), s[x].size()); i++) {
if (s[x][i] < t[i]) return true;
if (s[x][i] > t[i]) return false;
}
return true;
}
bool check3(int x, string t) {
for (int i = 1; i < min(t.size(), s[x].size()); i++) {
if (s[x][i] != t[i]) return false;
}
if (s[x].size() < t.size()) return false;
return true;
}
string conv(string s) {
for (int j = 0; j < s.size(); j++) {
if (s[j] == 'A') s[j] = '1';
else if (s[j] == 'C') s[j] = '2';
else if (s[j] == 'G') s[j] = '3';
else s[j] = '4';
}
return s;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
p[0] = 1;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = conv(s[i]);
s[i] = " " + s[i];
}
for (int i = 1; i <= 100000; i++) {
p[i] = p[i - 1] * 5 % mod;
}
sort(s + 1, s + n + 1);
for (int i = 1; i <= n; i++) {
a[i] = s[i].size() - 1;
vector<long long int> vv;
vv.push_back(0);
for (int j = 1; j <= a[i]; j++) {
vv.push_back((1ll * vv[j - 1] * 5 + (s[i][j] - '0')) % mod);
}
for (int j = 1; j <= a[i]; j++) {
long long int h = (vv[a[i]] - vv[j - 1] * p[a[i] - j + 1] % mod + mod) % mod;
update(1, 1, n, i, h);
}
}
for (int jj = 0; jj < q; jj++) {
long long int l = 1, r = n, h = -1, k = -1, c = 0;
string s, t;
cin >> s >> t;
s = conv(s);
t = conv(t);
s = " " + s;
t = " " + t;
for (int i = 1; i < t.size(); i++) {
c = (c * 5 + (t[i] - '0')) % mod;
}
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid, s) == true) {
r = mid - 1;
h = mid;
}
else l = mid + 1;
}
l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (check2(mid, s) == true) {
l = mid + 1;
k = mid;
}
else r = mid - 1;
}
if (!check3(h, s) || !check3(k, s)) cout << 0;
else {
cout << sum(1, 1, n, h, k, c);
}
cout << '\n';
}
}
Compilation message
selling_rna.cpp: In function 'bool check(int, std::string)':
selling_rna.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
28 | for (int i = 1; i < min(t.size(), s[x].size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool check2(int, std::string)':
selling_rna.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
35 | for (int i = 1; i < min(t.size(), s[x].size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool check3(int, std::string)':
selling_rna.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
42 | for (int i = 1; i < min(t.size(), s[x].size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'std::string conv(std::string)':
selling_rna.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int j = 0; j < s.size(); j++) {
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 1; i < t.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
29268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1600 ms |
337940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
47180 KB |
Output is correct |
| 2 |
Incorrect |
95 ms |
45820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
29268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
