Submission #1239928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239928		antromancap	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	136 ms	144984 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1, MX = 2e6 + 1;
int n, Q, mp[256], l[MX], r[MX], it[2][MX], child[2][MX][4], cnt[2];
string a[N];
vector<int> v[MX];

void add(int id, int i, string &s) {
	int u = 0;
	if (id) reverse(s.begin(), s.end());
	for (char ch : s) {
		int c = mp[ch];
		if (!child[id][u][c]) child[id][u][c] = ++cnt[id];
		u = child[id][u][c];
		if (id) v[u].push_back(i);
		else {
			if (!l[u]) l[u] = i;
			r[u] = i;
		}
	}
}

int find(int id, string &s) {
	int u = 0;
	if (id) reverse(s.begin(), s.end());
	for (char ch : s) {
		int c = mp[ch];
		if (!child[id][u][c]) return 0;
		u = child[id][u][c];
	}
	return u;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	mp['A'] = 0;
	mp['U'] = 1;
	mp['G'] = 2;
	mp['C'] = 3;
	cin >> n >> Q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		add(0, i, a[i]);
		add(1, i, a[i]);
	}
	for (int i = 1; i <= Q; i++) {
		string p, q;
		cin >> p >> q;
		int x = find(0, p);
		int y = find(1, q);
		cout << upper_bound(v[y].begin(), v[y].end(), r[x]) - lower_bound(v[y].begin(), v[y].end(), l[x]) << '\n';
	}
}

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