/* 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
const int MAXCH = 4; // charcters count
using nodeid = int;
struct Trie {
nodeid cur_node, rt;
int dfs_time;
nodeid nxt[MAXS][MAXCH];
int l[MAXS];
int r[MAXS];
vector<nodeid> end_node;
int ord(const char &ch) {
switch(ch) {
case 'A':
return 0;
case 'U':
return 1;
case 'C':
return 2;
case 'G':
return 3;
default:
return -1;
}
}
nodeid new_node() {
cur_node++;
return cur_node;
}
void init() {
memset(nxt, 0, sizeof(nxt));
memset(l, 0, sizeof(l));
memset(r, -1, sizeof(r));
cur_node = 0;
rt = new_node();
}
void insert(const string &s) {
int nd = rt;
for(const char &ch:s) {
nodeid &nnd = nxt[nd][ord(ch)];
if(!nnd) nnd = new_node();
nd = nnd;
}
end_node.eb(nd);
r[nd]++;
}
void _dfs(int nd) {
l[nd] += dfs_time;
r[nd] += dfs_time;
dfs_time = r[nd] + 1;
For(ch, 0, MAXCH - 1) {
nodeid nnd = nxt[nd][ch];
if(nnd) {
_dfs(nnd);
r[nd] = r[nnd];
}
}
}
void build(int* pos) {
dfs_time = 1;
_dfs(rt);
For(i, 0, sz(end_node) - 1) {
nodeid nd = end_node[i];
pos[i + 1] = l[nd];
}
}
pii find(const string &s) {
int nd = rt;
for(const char &ch:s) {
nodeid &nnd = nxt[nd][ord(ch)];
if(!nnd) return pii(-1, -1);
nd = nnd;
}
return pii(l[nd], r[nd]);
}
} tt, tr;
#define LO(x) ((x) & (-(x)))
struct BIT {
int n;
int a[MAXN];
void init(int _n) {
n = _n;
memset(a, 0, sizeof(a));
}
void add(int i, int x) {
while(i <= n) {
a[i] += x;
i += LO(i);
}
}
int ask(int i) {
int res = 0;
while(i) {
res += a[i];
i -= LO(i);
}
return res;
}
int ask(int l, int r) {
return ask(r) - ask(l - 1);
}
} bit;
struct SweepingLine {
struct Event {
int x, yl, yr, id;
}; vector<Event> ev;
int ans[MAXN];
void init() {
ev.clear();
memset(ans, 0, sizeof(ans));
}
void add_pt(int x, int y) {
ev.eb((Event){x, y, 0, 0});
}
void add_qry(int id, pii x, pii y) {
ev.eb((Event){x.F - 1, y.F, y.S, -id});
ev.eb((Event){x.S, y.F, y.S, id});
}
int* solve(int n) {
debug(sz(ev));
debug(&ev[0]);
sort(all(ev), [&](const Event &e1, const Event &e2) {
if(e1.x != e2.x) return e1.x < e2.x;
if(e1.id != e2.id) return e1.id < e2.id;
return false;
});
reverse(all(ev));
bit.init(n);
while(!ev.empty()) {
Event e = ev.back();
ev.pop_back();
if(e.id == 0) {
bit.add(e.yl, 1);
} else if(e.id > 0) {
ans[e.id] += bit.ask(e.yl, e.yr);
} else {
ans[-e.id] -= bit.ask(e.yl, e.yr);
}
}
return ans;
}
} swp;
int posx[MAXN];
int posy[MAXN];
int32_t main() {
NYA();
// nyaacho >/////<
cerr << (sizeof(tt) * 2 + sizeof(bit) + sizeof(swp) + sizeof(posx) * 2) << "\n";
int n, q; cin >> n >> q;
tt.init();
tr.init();
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) {
swp.add_qry(i, px, py);
}
}
int* ans = swp.solve(n);
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 |
Incorrect |
40 ms |
95020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
95392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
99792 KB |
Output is correct |
| 2 |
Correct |
55 ms |
97216 KB |
Output is correct |
| 3 |
Correct |
68 ms |
97956 KB |
Output is correct |
| 4 |
Correct |
55 ms |
97472 KB |
Output is correct |
| 5 |
Incorrect |
54 ms |
97280 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
95020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
