Submission #1273608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273608		trvhung	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	71 ms	17628 KiB

selling_rna

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int N = 1e5 + 5;
const int MAX = 2e6 + 5;
int n, m, curNode, pw[nMOD][N], hashQ1[N], res[N], ti[MAX], to[MAX], timeDfs;
string s[N], p[N], q[N];
pair<int, int> hashQ[N];
vector<int> at[N], adj[MAX];
vector<pair<int, int>> comp;

struct query {
	int idHash, idQuery;
	bool operator < (const query &other) const {
		return idHash < other.idHash;
	}
} Q[N];

struct node {
	node *child[26];
	int id, h, cnt;
	node() {
		for (int i = 0; i < 26; ++i) child[i] = nullptr;
		id = h = cnt = 0;
	}
};

node *root = new node();

void add(string &x) {
	node *u = root;
	for (auto c: x) {
		int k = c - 'A';
		
		if (u -> child[k] == nullptr) {
			u -> child[k] = new node();
			u -> child[k] -> id = ++curNode;
			u -> child[k] -> h = u -> h + 1;
			adj[u -> id].push_back(u -> child[k] -> id);
		}

		u = u -> child[k];
		u -> cnt++;
	}
}

void trav(string &x) {
	vector<pair<int, char>> path;
	node *u = root;

	for (auto c: x) {
		int k = c - 'A';
		path.push_back(make_pair(u -> id, c));
		u = u -> child[k];
	}

	pair<int, int> H = make_pair(0, 0);
	int cur = u -> id, len = 0;
	reverse(path.begin(), path.end());

	for (auto p: path) {
		int v = p.F;
		char c = p.S;

		H.F = (1LL * (c - 'A' + 1) * pw[0][len] + H.F) % mods[0];
		H.S = (1LL * (c - 'A' + 1) * pw[1][len] + H.S) % mods[1];

		int pos = lower_bound(comp.begin(), comp.end(), H) - comp.begin();
		if (pos < (int) comp.size() && comp[pos] == H)
			at[pos + 1].push_back(cur);

		cur = v;
		len++;
	}
}

void precalc() {
	for (int i = 0; i < nMOD; ++i) {
		pw[i][0] = 1;
		for (int j = 1; j < N; ++j)
			pw[i][j] = 1LL * pw[i][j - 1] * base % mods[i];
	}
}

void calcHash(string &x, pair<int, int> &H) {
	int len = (int) x.size();
	for (int i = 1; i <= len; ++i) {
		H.F = (1LL * H.F * base + x[i - 1] - 'A' + 1) % mods[0];
		H.S = (1LL * H.S * base + x[i - 1] - 'A' + 1) % mods[1];
	}
}

void compressHashQ() {
	for (int i = 1; i <= m; ++i)
		comp.push_back(hashQ[i]);

	sort(comp.begin(), comp.end());
	comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

	for (int i = 1; i <= m; ++i)
		hashQ1[i] = lower_bound(comp.begin(), comp.end(), hashQ[i]) - comp.begin() + 1;
}

void dfs(int u) {
	ti[u] = ++timeDfs;
	for (int v: adj[u])
		dfs(v);
	to[u] = timeDfs;
}

struct BIT {
	int bit[MAX];

	void update(int id, int v) {
		for (; id <= curNode; id += id & -id)
			bit[id] += v;
	}

	int get(int id) {
		int res = 0;
		for (; id > 0; id -= id & -id)
			res += bit[id];
		return res;
	}

	void updateRange(int l, int r, int v) {
		update(l, v); update(r + 1, -v);
	}

	int getRange(int l, int r) {
		if (l > r) return 0;
		return get(r) - get(l - 1);
	}
} bit_depth, bit;

void updateAns(int i) {
	int len = (int) q[i].size(), pr;
	vector<pair<int, int>> path;

	node *u = root;
	path.push_back(make_pair(u -> id, u -> h));
	for (auto c: p[i]) {
		int k = c - 'A';
		if (u -> child[k] == nullptr) return;
		u = u -> child[k];
		path.push_back(make_pair(u -> id, u -> h));
	}

	for (int i = 0; i < (int) path.size(); ++i)
		if (path[i].S >= u -> h - len + 1) {
			pr = i == 0 ? -1 : path[i - 1].F;
			break;
		}

	res[i] = bit_depth.get(ti[u -> id]) - (pr == -1 ? 0 : bit_depth.get(ti[pr])) + bit.getRange(ti[u -> id] + 1, to[u -> id]);
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		add(s[i]);
	}

	precalc();
	for (int i = 1; i <= m; ++i) {
		cin >> p[i] >> q[i];
		calcHash(q[i], hashQ[i]);
	}

	compressHashQ();

	for (int i = 1; i <= n; ++i)
		trav(s[i]);

	dfs(0);

	for (int i = 1; i <= m; ++i) {
		Q[i].idHash = hashQ1[i];
		Q[i].idQuery = i;
	}

	sort(Q + 1, Q + 1 + m);
	int ptr = 1;
	curNode++;

	while (ptr <= m) {
		for (int x: at[Q[ptr].idHash]) {
			bit_depth.updateRange(ti[x], to[x], 1);
			bit.update(ti[x], 1);
		}

		int j = ptr;
		updateAns(Q[ptr].idQuery);
		while (j < m && Q[j + 1].idHash == Q[j].idHash) {
			updateAns(Q[++j].idQuery);
		}

		for (int x: at[Q[ptr].idHash]) {
			bit_depth.updateRange(ti[x], to[x], -1);
			bit.update(ti[x], -1);
		}

		ptr = j + 1;
	}

	for (int i = 1; i <= m; ++i)
		cout << res[i] << el;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40