#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
#define mp make_pair
typedef long long ll;
typedef pair<int, int > pii;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/*************************JOI16_selling_rna***************************************/
int N, M, ans[100001];
int conv(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'U') return 2;
return 3;
}
struct Node {
int nxt[4];
v<int> str;
Node() { memset(nxt, -1, sizeof nxt); }
v<int> getChildren() {
v<int> chi;
FOR(i, 0, 4) if (nxt[i] != -1) chi.push_back(nxt[i]);
return chi;
}
};
struct Trie {
Node t[4000009];
int tsz = 1;
int dfstim = 0;
int P[100001]; // for -(1-N)
int L[100001], R[100001]; // for +(1-M)
void addTrieNode(string &s, int num) {
int cur = 0;
for (char &cc : s) {
int c = conv(cc);
if (t[cur].nxt[c] == -1)
t[cur].nxt[c] = tsz++;
cur = t[cur].nxt[c];
}
t[cur].str.push_back(num);
}
void dfs(int cur) {
if (t[cur].str.size()>0)
dfstim++;
for (int x : t[cur].str)
if (x < 0) P[abs(x)] = dfstim;
else L[x] = dfstim;
v<int> adj = t[cur].getChildren();
for (auto nex : adj)
dfs(nex);
if (t[cur].str.size()>0)
dfstim++;
for (int x : t[cur].str)
if (x > 0) R[x] = dfstim;
}
} tfor, trev;
struct events {
int x, y, fl;
events(int _x, int _y, int _fl) : x(_x), y(_y), fl(_fl) {}
};
const int L = 200009;
int bit[L + 1];
void upd(int k, int val) {
for (k++; k <= L; k += (k&-k))
bit[k] += val;
}
int query(int k) {
int temp = 0;
for (k++; k > 0; k -= (k&-k))
temp += bit[k];
return temp;
}
int main() {
io();
cin >> N >> M;
FORE(i, 1, N) {
string s; cin >> s;
tfor.addTrieNode(s, -i);
reverse(all(s));
trev.addTrieNode(s, -i);
}
FORE(i, 1, M) {
string p, q; cin >> p >> q;
tfor.addTrieNode(p, i);
reverse(all(q));
trev.addTrieNode(q, i);
}
tfor.dfs(0);
trev.dfs(0);
//FORE(i, 1, N) {
// printf("org str; point @ (%d, %d) \n", tfor.P[i], trev.P[i]);
//}
//FORE(i, 1, M) {
// printf("org query; rect @ x(%d, %d), y(%d, %d) \n", tfor.L[i], tfor.R[i], trev.L[i], trev.R[i]);
//}
//FORE(i, 1, M) {
// int ans = 0;
// FORE(k, 1, N) if (tfor.L[i] <= tfor.P[k] && tfor.P[k] <= tfor.R[i] && trev.L[i] <= trev.P[k] && trev.P[k] <= trev.R[i])
// ans++;
// cout << ans << "\n";
//}
v<events> alle;
alle.reserve(N + 4 * M);
FORE(i, 1, N)
alle.push_back(events(tfor.P[i], trev.P[i], INT_MIN));
FORE(i, 1, M) {
alle.push_back(events(tfor.R[i], trev.R[i], +i));
alle.push_back(events(tfor.L[i] - 1, trev.R[i], -i));
alle.push_back(events(tfor.R[i], trev.L[i] - 1, -i));
alle.push_back(events(tfor.L[i] - 1, trev.L[i] - 1, +i));
}
sort(all(alle), [](events &a, events &b) {
return mp(a.x, a.fl) < mp(b.x, b.fl);
});
for (auto e : alle) {
if (e.fl == INT_MIN)
upd(e.y, 1);
else if (e.fl < 0)
ans[abs(e.fl)] -= query(e.y);
else
ans[e.fl] += query(e.y);
}
FORE(i, 1, M)
cout << ans[i];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
779 ms |
313528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
578 ms |
314492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
507 ms |
319256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
779 ms |
313528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
