#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
string s[100005];
multiset<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].insert(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].insert(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].count(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;
}
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] = " " + s[i];
s[i] = conv(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++) {
vector<int> v;
v.push_back(0);
for (int j = 1; j < s[i].size(); j++) {
v[j] = v[j - 1] * 5 + (s[i][j] - '0');
v[j] %= mod;
}
for (int j = 1; j < s[i].size(); j++) {
update(1, 1, n, i, (v[s[i].size() - 1] - v[j - 1] * p[s[i].size() - j] % mod + mod) % mod);
}
}
for (int jj = 0; jj < q; jj++) {
int l = 1, r = n, h = -1, k = -1, c = 0;
string s, t;
cin >> s >> t;
s = " " + s;
t = " " + t;
s = conv(s);
t = conv(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 (h == -1 || k == -1) 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 'std::string conv(std::string)':
selling_rna.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0; j < s.size(); j++) {
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int j = 1; j < s[i].size(); j++) {
| ~~^~~~~~~~~~~~~
selling_rna.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = 1; j < s[i].size(); j++) {
| ~~^~~~~~~~~~~~~
selling_rna.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 1; i < t.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
216 ms |
129012 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1577 ms |
101404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
