#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define heap_max(a) priority_queue<a>
#define heap_max(a) priority_queue<a,vector<a>,greater<a>>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e6 + 10;
int n, q, l, r;
string s[N];
struct Trie {
struct Node {
Node* child[30];
int cnt;
vector<int>mem;
Node () {
for (int i = 0; i <= 26; ++i) child[i] = nullptr;
cnt = 0;
mem = {};
};
};
Node* root = new Node();
void add (string s, int idx) {
Node* p = root;
for (int i = 0; i < isz(s); ++i) {
int c = (s[i] - 'A');
if (p -> child[c] == nullptr) {
p -> child[c] = new Node();
}
p = p -> child[c];
p -> mem.push_back(idx);
}
}
void get_prefix (string s) {
Node* p = root;
for (int i = 0; i < isz(s); ++i) {
int c = (s[i] - 'A');
if (p -> child[c] == nullptr) {
return;
}
p = p -> child[c];
}
l = p -> mem.front();
r = p -> mem.back();
return;
}
int get_sufix (string s) {
Node* p = root;
for (int i = 0; i < isz(s); ++i) {
int c = (s[i] - 'A');
if (p -> child[c] == nullptr) {
return 0;
}
p = p -> child[c];
}
int left = lower_bound(ALL(p->mem), l)-p->mem.begin();
int right = upper_bound(ALL(p->mem), r)-p->mem.begin()-1;
return right - left + 1;
}
} tree1, tree2;
int main () {
// file("dynamic");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
FOR(i,1,n) cin >> s[i];
sort(s + 1, s + n + 1);
for (int i = 1; i <= n; ++i) tree1.add(s[i], i);
for (int i = 1; i <= n; ++i) {
string rev = s[i];
reverse(ALL(rev));
tree2.add(rev, i);
}
while(q--) {
string x, y; cin >> x >> y;
l = -1; r = -1;
tree1.get_prefix(x);
if (l == -1) {
cout << 0 << '\n';
continue;
}
cout << tree2.get_sufix(y) << '\n';
}
}
Compilation message
selling_rna.cpp:16: warning: "heap_max" redefined
16 | #define heap_max(a) priority_queue<a,vector<a>,greater<a>>
|
selling_rna.cpp:15: note: this is the location of the previous definition
15 | #define heap_max(a) priority_queue<a>
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
31836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
377 ms |
662312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
32928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
31836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
