#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
//const int M = 2e6 + 5;
const int oo = 1e9;
int n, m;
string s[N], a[N], b[N];
char change(char c){
if(c == 'A') return '1';
if(c == 'C') return '2';
if(c == 'G') return '3';
return '4';
}
struct trie{
trie* child[6];
vector<int> w;
trie(){
for(int i = 0; i <= 5; i ++) child[i] = NULL;
w.clear();
}
};
trie* root;
void add(string &x,int id){
trie* p = root;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL){
p -> child[val] = new trie();
}
p = p -> child[val];
p -> w.push_back(id);
}
}
int query(string &x,int l,int r){
trie* p = root;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) return 0;
p = p -> child[val];
}
// cerr << x << " " << l << " " << r << " t\n";
// for(auto j : p -> w) cerr << j << " ";
// cerr << "\n";
auto v = upper_bound(p -> w.begin(), p -> w.end(), r);
auto u = lower_bound(p -> w.begin(), p -> w.end(), l);
if(v == p -> w.begin()) return 0;
if(u == p -> w.end()) return 0;
v--;
int tu = u - p -> w.begin();
int tv = v - p -> w.begin();
if(tu <= tv) return tv - tu + 1;
return 0;
}
mt19937 rd(15253524352);
int ra(int l,int r){
return l + rd() % (r - l + 1);
}
const ll mod[2] = {ra(1e9, 2e9), (int)1e9 + 7};
const ll base = 137;
map<ll,int> mx, mi;
int le[N], ri[N];
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
root = new trie();
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> s[i];
for(int j = 0; j < s[i].size(); j ++){
s[i][j] = change(s[i][j]);
}
}
sort(s + 1, s + n + 1);
// for(int i = 1; i <= n; i ++) cerr << s[i] << "\n";
for(int i = 1; i <= n; i ++){
ll h[2];
h[0] = h[1] = 0;
for(int j : s[i]){
for(int k = 0; k <= 1; k ++){
h[k] = (1ll * h[k] * base % mod[k] + (ll)(j - '0')) % mod[k];
}
ll H = 1ll * h[0] * mod[1] + h[1];
mx[H] = i;
if(mi[H] == 0) mi[H] = i;
}
string hk = s[i];
reverse(hk.begin(), hk.end());
// cerr << i << " j\n";
// for(auto j : s[i]) cerr
add(hk, i);
}
for(int i = 1; i <= m; i ++){
cin >> a[i] >> b[i];
for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
ll h[2];
h[0] = h[1] = 0;
for(int j : a[i]){
for(int k = 0; k <= 1; k ++){
h[k] = (h[k] * base % mod[k] + (int)(j - '0')) % mod[k];
}
}
ll H = 1ll * h[0] * mod[1] + h[1];
le[i] = mi[H], ri[i] = mx[H];
if(!le[i]){
cout << 0 << "\n";
continue;
}
// cerr << i << " " << le[i] << " " << ri[i] << " o\n";
reverse(b[i].begin(), b[i].end());
cout << query(b[i], le[i], ri[i]) << "\n";
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j = 0; j < s[i].size(); j ++){
| ~~^~~~~~~~~~~~~
selling_rna.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
| ~~^~~~~~~~~~~~~
selling_rna.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
| ~~^~~~~~~~~~~~~
selling_rna.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 2 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 3 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 4 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 5 |
Correct |
3 ms |
10488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 7 |
Correct |
3 ms |
10320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
526 ms |
230728 KB |
Output is correct |
| 2 |
Correct |
427 ms |
223048 KB |
Output is correct |
| 3 |
Execution timed out |
1571 ms |
198248 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
11468 KB |
Output is correct |
| 2 |
Correct |
19 ms |
11600 KB |
Output is correct |
| 3 |
Correct |
22 ms |
11872 KB |
Output is correct |
| 4 |
Correct |
16 ms |
11600 KB |
Output is correct |
| 5 |
Correct |
21 ms |
12132 KB |
Output is correct |
| 6 |
Correct |
23 ms |
11856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 2 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 3 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 4 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 5 |
Correct |
3 ms |
10488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 7 |
Correct |
3 ms |
10320 KB |
Output is correct |
| 8 |
Correct |
526 ms |
230728 KB |
Output is correct |
| 9 |
Correct |
427 ms |
223048 KB |
Output is correct |
| 10 |
Execution timed out |
1571 ms |
198248 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
