Submission #1028538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028538		VectorLi	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	158 ms	156668 KiB

selling_rna

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = (int) 1E5;
const int K = (int) 2E6;

int index(char c) {
	if (c == 'A') {
		return 0;
	}
	if (c == 'G') {
		return 1;
	}
	if (c == 'C') {
		return 2;
	}
	if (c == 'U') {
		return 3;
	}
	return -1;
}

int x[2];
int e[2][K + 1][4];
int l[K + 1], r[K + 1];
vector<int> a[K + 1];

void insert(string s, int p, int t) {
	int u = 0;
	for (int i = 0; i < (int) s.size(); i++) {
		if (t == 0) {
			l[u] = l[u] >= 0 ? l[u] : p;
			r[u] = max(r[u], p);
		} else {
			a[u].push_back(p);
		}
		int &v = e[t][u][index(s[i])];
		if (v == 0) {
			v = ++x[t];
		}
		u = v;
	}
	if (t == 0) {
		l[u] = l[u] >= 0 ? l[u] : p;
		r[u] = max(r[u], p);
	} else {
		a[u].push_back(p);
	}
}

int find(string s, int t) {
	int u = 0;
	for (int i = 0; i < (int) s.size(); i++) {
		int v = e[t][u][index(s[i])];
		if (v == 0) {
			return -1;
		}
		u = v;
	}
	return u;
}

int n, k;
string s[N];

int main() {
#ifdef LOCAL
	freopen("A.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	sort(s, s + n);
	memset(l, -1, sizeof(l));
	for (int i = 0; i < n; i++) {
		insert(s[i], i, 0);
		reverse(s[i].begin(), s[i].end());
		insert(s[i], i, 1);
	}
	
	for (int i = 0; i < k; i++) {
		string t0, t1;
		cin >> t0 >> t1;
		reverse(t1.begin(), t1.end());
		int p0 = find(t0, 0), p1 = find(t1, 1);
		if (p0 < 0 || p1 < 0) {
			cout << 0 << "\n";
		} else {
			auto i0 = upper_bound(a[p1].begin(), a[p1].end(), r[p0]);
			auto i1 = lower_bound(a[p1].begin(), a[p1].end(), l[p0]);
			cout << (int) (i0 - i1) << "\n";
		}
	}
	
	return 0;
}

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