/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/
#include<bits/stdc++.h>
using namespace std;
void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
if (fopen(filein.c_str(), "r")){
freopen(filein.c_str(), "r", stdin);
freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
freopen(fileerr.c_str(), "w", stderr);
#endif
}
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}
void Hollwo_Pelw();
signed main(){
#ifdef hollwo_pelw_local
FAST_IO("input.inp", "output.out", "error.err");
auto start = chrono::steady_clock::now();
#else
FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
#ifdef hollwo_pelw_local
auto end = chrono::steady_clock::now();
cout << endl;
cout << "Excution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
return 0;
}
const int N = 2e6 + 5;
inline int toint(char c){
return (c > 'A') + (c > 'C') + (c > 'G') + (c > 'U');
}
int bit[N];
inline void add(int x, int v) {
for (++ x; x < N; x += x & -x)
bit[x] += v;
}
inline int query(int x) {
int r = 0;
for (; x; x -= x & -x)
r += bit[x];
return r;
}
inline int query(int l, int r) {
return query(r) - query(l - 1);
}
// x < y && ok
bool comp(const string &x, const string &y, bool ok) {
int n = min(x.size(), y.size());
for (int i = 0; i < n; i++) {
if (x[i] > y[i]) return 0;
if (x[i] < y[i]) return 1;
}
return ok;
}
bool comp1(const string &x, const string &y) {
int n = min(x.size(), y.size());
for (int i = 0; i < n; i++) {
if (x[i] > y[i]) return 1;
if (x[i] < y[i]) return 0;
}
return 0;
}
int n, q, id[N], pos[N], ans[N];
int adj[N][4], nodecnt;
int tin[N], tout[N], timer;
string a[N], s[N], e[N];
void dfs(int u) {
tin[u] = ++ timer;
for (int i = 0; i < 4; i++)
if (adj[u][i]) dfs(adj[u][i]);
tout[u] = timer;
}
void Hollwo_Pelw() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= q; i++) {
cin >> s[i] >> e[i], id[i] = i;
}
sort(a + 1, a + n + 1);
sort(id + 1, id + q + 1, [](const int &x, const int &y){
return pair<string, string>(s[x], e[x]) < pair<string, string>(s[y], e[y]);
});
for (int i = 1; i <= n; i ++) {
reverse(a[i].begin(), a[i].end());
int &p = pos[i];
for (auto c : a[i]) {
if (!adj[p][toint(c)])
adj[p][toint(c)] = ++ nodecnt;
p = adj[p][toint(c)];
}
reverse(a[i].begin(), a[i].end());
}
dfs(0);
int l = 1, r = 1;
for (int _ = 1; _ <= q; _++) {
int i = id[_];
while (r <= n && comp(s[i], a[r], 1)) add(pos[r ++], +1);
while (l <= r && comp(a[l], s[i], 0)) add(pos[l ++], -1);
while (r >= l && comp1(s[i], a[r-1])) add(pos[-- r], -1);
reverse(e[i].begin(), e[i].end());
int p = 0, ok = 1;
for (auto c : e[i]) {
if (!adj[p][toint(c)]) {
ok = 0; break;
}
p = adj[p][toint(c)];
}
ans[i] = (ok ? query(tin[p], tout[p]) : 0);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
Compilation message
selling_rna.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
selling_rna.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen(filein.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen(fileout.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
188232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
245036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
189052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
188232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
