Submission #1289517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289517		am_aadvik	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	467 ms	386956 KiB

selling_rna

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node {
	int idx; 
	vector<pair<int, int>> a;
	vector<int> nxt;
	node(int i) { idx = i, nxt.resize(26, -1); }
};
string strip(string& s, int k) { string t; for (int i = 0; i < min((int)s.length(), k); ++i) t += s[i]; return t; }
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, q, m = 1; cin >> n >> q;
	vector<string> a(n);
	for (auto &x : a) cin >> x;
	sort(a.begin(), a.end());

	vector<node> arr;
	arr.push_back((0));
	for (int i = 0; i < n; ++i) {
		int cur = 0, mi = a[i].length();
		arr[cur].a.push_back({ i, arr[cur].a.size() });
		for (int k = 0; k < mi; ++k) {
			int j = (mi - k - 1);
			if (arr[cur].nxt[(a[i][j] - 'A')] == -1)
				arr[cur].nxt[(a[i][j] - 'A')] = m, arr.push_back((m)), cur = m, m++;
			else cur = arr[cur].nxt[(a[i][j] - 'A')];
			arr[cur].a.push_back({ i, arr[cur].a.size() });
		}
	}
	while (q--) {
		string s, t; cin >> s >> t;
		reverse(t.begin(), t.end());
		int l = 0, r = n - 1, si = n, ei = 0;
		while (l <= r) {
			int m = (l + r) / 2;
			if (strip(a[m], s.length()) < s) l = m + 1;
			else si = m, r = m - 1;
		}
		l = 0, r = n - 1;
		while (l <= r) {
			int m = (l + r) / 2;
			if (strip(a[m], s.length()) > s) r = m - 1;
			else ei = m, l = m + 1;
		}
		int idx = 0;
		for (int i = 0; i < t.length(); ++i) {
			if (idx == -1) break;
			idx = arr[idx].nxt[t[i] - 'A'];
		}
		if ((idx == -1) || (si > ei)) { cout << 0 << endl; continue; }
		auto f = lower_bound(arr[idx].a.begin(), arr[idx].a.end(), make_pair(si, -1));
		auto e = lower_bound(arr[idx].a.begin(), arr[idx].a.end(), make_pair(ei, n + n));
		if ((f == arr[idx].a.end()) || (e == arr[idx].a.begin())) { cout << 0 << endl; continue; }
		cout << ((*prev(e)).second - (*f).second + 1) << endl;
	}
}

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