/*
ID: varunra2
LANG: C++
TASK: rna
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set_less = tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>;
using ordered_set_equal = tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update>;
using ordered_map =
tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
const int RANDOM =
chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<int, int, chash> table;
mt19937 rng(
(unsigned int)chrono::steady_clock::now().time_since_epoch().count());
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
VI hsh(string& s) {
VI ret(sz(s) + 1, 1);
map<char, int> mp;
mp['A'] = 1;
mp['G'] = 2;
mp['C'] = 3;
mp['U'] = 4;
trav(x, mp) x.y--;
for (int i = 0; i < sz(s); i++) {
ret[i + 1] = (1ll * ret[i] * 4 + mp[s[i]]) % MOD;
}
return ret;
}
VS vals;
VS valsrev;
VVI valshsh;
VVI valshshrev;
vector<pair<string, string>> qrys;
vector<pair<VI, VI>> qryshsh;
VI ret;
int n, m;
void init() {
vals.resize(n);
valsrev.resize(n);
valshshrev.resize(n);
qrys.resize(m);
valshsh.resize(n);
qryshsh.resize(m);
ret.assign(m, 0);
}
unordered_map<int, int> cmp;
int siz = 0;
void comp(VI& hshs) {
sort(all(hshs));
hshs.resize(unique(all(hshs)) - hshs.begin());
for (int i = 0; i < sz(hshs); i++) {
cmp[hshs[i]] = i;
}
if (siz == 0) siz = sz(hshs);
}
VVI adj;
vector<unordered_map<int, int>> merg;
VVI qryind;
VVI updind;
void init2() {
adj.resize(siz);
merg.resize(siz);
qryind.resize(siz);
updind.resize(siz);
}
void swp(unordered_map<int, int>& i, unordered_map<int, int>& j) {
if (sz(i) < sz(j)) {
swap(i, j);
}
for (auto& x : j) {
i[x.x] += x.y;
}
}
void dfs(int u, bool need, vector<int>& vls) {
bool have = (sz(qryind[u]) > 0) or need;
for (auto& x : qryind[u]) {
vls[qryshsh[x].y.back()]++;
}
if (have) {
for (auto& x : updind[u]) {
for (auto& y : valshshrev[x]) {
if (vls[y]) merg[u][y]++;
}
}
}
for (auto& x : adj[u]) {
dfs(x, have, vls);
if (have) swp(merg[u], merg[x]);
}
for (auto& x : qryind[u]) {
ret[x] = merg[u][qryshsh[x].y.back()];
vls[qryshsh[x].y.back()]--;
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
init();
for (int i = 0; i < n; i++) {
cin >> vals[i];
valsrev[i] = vals[i];
reverse(all(valsrev[i]));
valshsh[i] = hsh(vals[i]);
valshshrev[i] = hsh(valsrev[i]);
}
for (int i = 0; i < m; i++) {
cin >> qrys[i].x >> qrys[i].y;
reverse(all(qrys[i].y));
qryshsh[i].x = hsh(qrys[i].x);
qryshsh[i].y = hsh(qrys[i].y);
}
VI hshs;
for (int i = 0; i < n; i++) {
for (int j = 0; j < sz(valshsh[i]); j++) {
hshs.PB(valshsh[i][j]);
hshs.PB(valshshrev[i][j]);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < sz(qryshsh[i].x); j++) {
hshs.PB(qryshsh[i].x[j]);
}
for (int j = 0; j < sz(qryshsh[i].y); j++) {
hshs.PB(qryshsh[i].y[j]);
}
}
comp(hshs);
for (int i = 0; i < n; i++) {
trav(x, valshsh[i]) { x = cmp[x]; }
}
for (int i = 0; i < m; i++) {
trav(x, qryshsh[i].x) { x = cmp[x]; }
trav(x, qryshsh[i].y) { x = cmp[x]; }
}
for (int i = 0; i < n; i++) {
trav(x, valshshrev[i]) { x = cmp[x]; }
}
// hashing and compression done, make the tree and then do small to large
init2();
for (int i = 0; i < n; i++) {
for (int j = 0; j < sz(valshsh[i]) - 1; j++) {
adj[valshsh[i][j]].PB(valshsh[i][j + 1]);
}
}
for (int i = 0; i < siz; i++) {
sort(all(adj[i]));
adj[i].resize(unique(all(adj[i])) - adj[i].begin());
}
// made the tree, let's do the leaves
for (int i = 0; i < n; i++) {
updind[valshsh[i].back()].PB(i);
}
// now let's preprocess queries
for (int i = 0; i < m; i++) {
qryind[qryshsh[i].x.back()].PB(i);
}
VI xx(siz, 0);
dfs(0, false, xx);
for (int i = 0; i < m; i++) {
cout << ret[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1593 ms |
134576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
22324 KB |
Output is correct |
| 2 |
Correct |
92 ms |
15388 KB |
Output is correct |
| 3 |
Correct |
107 ms |
19168 KB |
Output is correct |
| 4 |
Correct |
87 ms |
16528 KB |
Output is correct |
| 5 |
Correct |
99 ms |
15320 KB |
Output is correct |
| 6 |
Correct |
112 ms |
19140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Execution timed out |
1593 ms |
134576 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
