#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
//#pragma expected_value
//#pragma isolated_call
//#pragma disjoint
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define setpre(i) setprecision(i)<<fixed
#define foru(i, a, b) for(int i=a;i<=b;++i)
#define ford(i, a, b) for(int i=a;i>=b;--i)
#define mp make_pair
#define moo cout<<"moo "
#define fi first
#define se second
ll lmod = 1e9 + 7;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int, int> ii;
typedef pair<double, double> dd;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
vector<string> s;
int getid(char c){
if(c == 'A') return 0;
if(c == 'U') return 1;
if(c == 'G') return 2;
return 3;
}
struct node{
int next[4];
int l, r;
node(){
memset(next, -1, sizeof next);
l = INT_MAX;
r = -1;
}
};
struct node2{
int next[4];
ordered_set os;
node2(){
memset(next, -1, sizeof next);
}
};
struct {
vector<node> t;
void init(){
t.emplace_back();
}
void insert(int id){
int ptr = 0;
for(char c: s[id]){
if(t[ptr].next[getid(c)] == -1){
t.emplace_back();
t[ptr].next[getid(c)] = t.size() - 1;
}
ptr = t[ptr].next[getid(c)];
t[ptr].l = min(t[ptr].l, id);
t[ptr].r = max(t[ptr].l, id);
}
}
int traverse(string z){
int ptr = 0;
for(char c: z){
if(t[ptr].next[getid(c)] == -1) return -1;
ptr = t[ptr].next[getid(c)];
}
return ptr;
}
} trie1;
struct {
vector<node2> t;
void init(){
t.emplace_back();
}
void insert(int id){
int ptr = 0;
for(char c: s[id]){
if(t[ptr].next[getid(c)] == -1){
t.emplace_back();
t[ptr].next[getid(c)] = t.size() - 1;
}
ptr = t[ptr].next[getid(c)];
t[ptr].os.insert(id);
}
}
int traverse(string z){
int ptr = 0;
for(char c: z){
if(t[ptr].next[getid(c)] == -1) return -1;
ptr = t[ptr].next[getid(c)];
}
return ptr;
}
} trie2;
int main(){
// freopen("input.inp", "r", stdin);
// freopen("output.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
foru(i, 1, n){
string z; cin >> z;
s.pb(z);
}
trie1.init(); trie2.init();
sort(s.begin(), s.end());
foru(i, 0, n - 1) {
trie1.insert(i);
reverse(s[i].begin(), s[i].end());
trie2.insert(i);
}
while(q--){
string z, t; cin >> z >> t;
reverse(t.begin(), t.end());
int a = trie1.traverse(z);
int b = trie2.traverse(t);
if(a == -1 or b == -1){
cout << 0 << endl; continue;
}
int l = trie1.t[a].l;
int r = trie1.t[a].r;
cout << trie2.t[a].os.order_of_key(r + 1) - trie2.t[a].os.order_of_key(l) << endl;
}
// fclose(stdout);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
302360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
70 ms |
10260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
