/* code by PixelCat */
/* meow owo */
#include <bits/stdc++.h>
#define int LL //__int128
#define double long double
using namespace std;
using LL = long long;
// using i128 = __int128_t;
using ull = unsigned long long;
using pii = pair<int, int>;
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair
#define MOD (int)(998244353)
// #define MOD (int)((LL)1'000'000'007)
#define INF (int)(4e18)
#define EPS (1e-6)
namespace PixelCat {
#ifdef NYAOWO
#include "/home/pixelcat/yodayo/meow/library/debug.hpp"
inline void USACO(const string &s) {
cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
#endif
inline void NYA() {
ios::sync_with_stdio(false);
cin.tie(0);
}
inline int gcd(int a, int b) {
return __gcd(a, b);
}
inline int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod = MOD) {
int ans = 1;
for (; p; p >>= 1, b = b * b % mod)
if (p & 1) ans = ans * b % mod;
return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
if (_b > _a) _a = _b;
}
mt19937_64 rng(
chrono::steady_clock::now().time_since_epoch().count());
} // namespace PixelCat
using namespace PixelCat;
const int MAXN = 100010; // N, Q
const int MAXS = 2000010; // total # of characters
struct Trie {
vector<pair<string, int>> vs;
void insert(const string &s) {
vs.eb(s, sz(vs) + 1);
}
// void _dfs(int nd);
void build(int* pos) {
int n = sz(vs);
sort(all(vs));
For(i, 0, n - 1) pos[vs[i].S] = i + 1;
}
bool beginswith(const string &sa, const string &sb) {
if(sz(sa) < sz(sb)) return false;
For(i, 0, sz(sb) - 1) {
if(sa[i] != sb[i]) return false;
}
return true;
}
pii find(const string &s) {
int l = -1, r = -1;
For(i, 0, sz(vs) - 1) {
if(beginswith(vs[i].F, s)) {
if(l < 0) l = i + 1;
r = i + 1;
}
}
return pii(l, r);
}
} tt, tr;
// struct BIT {
// void init(int n);
// void add(int i, int x);
// int ask(int i);
// int ask(int l, int r);
// } bit;
struct SweepingLine {
vector<pii> pt;
int ans[MAXN];
void init() {
memset(ans, -1, sizeof(ans));
}
void add_pt(int x, int y) {
pt.eb(x, y);
}
void add_qry(int id, pii x, pii y) {
int cnt = 0;
for(auto &i:pt) {
if(x.F <= i.F && i.F <= x.S &&
y.F <= i.S && i.S <= y.S) {
cnt++;
}
}
ans[id] = cnt;
}
void solve(int n, int* res) {
For(i, 1, n) if(ans[i] >= 0) res[i] = ans[i];
}
} swp;
int posx[MAXN];
int posy[MAXN];
int ans[MAXN];
int32_t main() {
NYA();
// nyaacho >/////<
int n, q; cin >> n >> q;
For(i, 1, n) {
string s; cin >> s;
tt.insert(s);
reverse(all(s));
tr.insert(s);
}
tt.build(posx);
tr.build(posy);
swp.init();
For(i, 1, n) {
swp.add_pt(posx[i], posy[i]);
}
For(i, 1, q) {
string sx, sy;
cin >> sx >> sy;
pii px = tt.find(sx);
reverse(all(sy));
pii py = tr.find(sy);
if(px.F < 0 || py.F < 0) {
ans[i] = 0;
} else {
swp.add_qry(i, px, py);
}
}
swp.solve(q, ans);
For(i, 1, q) {
cout << ans[i] << "\n";
}
return 0;
}
/*
2 3
AUGC
AGC
G C
AU C
A C
=> 0 1 2
3 3
AA
AA
AGA
AA AA
AG GA
AG GA
=> 2 1 1
8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
=> 1 0 1 2 3 2 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
872 ms |
9192 KB |
Output is correct |
| 2 |
Execution timed out |
1574 ms |
9452 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1571 ms |
7968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 8 |
Correct |
872 ms |
9192 KB |
Output is correct |
| 9 |
Execution timed out |
1574 ms |
9452 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
