Submission #870404

#	Time	Username	Problem	Language	Result	Execution time	Memory
870404		serifefedartar	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	621 ms	504652 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 100;

int no[MAXN];
int last_given = 0;

struct Node {
	Node *to[4];
	vector<int> v;
	vector<int> last;
	void srt() {
		sort(v.begin(), v.end());
		for (int i = 0; i < 4; i++) {
			if (to[i] != NULL)
				to[i]->srt();
		}
	}
	void dfs() {
		for (auto u : last) {
			last_given++;
			no[u] = last_given;
		}

		for (int i = 0; i < 4; i++) {
			if (to[i] != NULL)
				to[i]->dfs();
		}
	}
};

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

vector<string> vs;
int main() {
	int N, M;
	cin >> N >> M;

	Node *root = new Node();
	Node *root_rev = new Node();
	vs = vector<string>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> vs[i];

		Node *now = root;
		now->v.push_back(i);
		for (auto u : vs[i]) {
			int q = c(u);
			if (now->to[q] == NULL)
				now->to[q] = new Node();
			now = now->to[q];
			now->v.push_back(i);
		}
		now->last.push_back(i);
	}
	root->dfs();

	for (int i = 1; i <= N; i++) {
		int q = no[i];
		Node *now = root_rev;
		now->v.push_back(q);

		int len = vs[i].length();
		for (int j = len-1; j >= 0; j--) {
			int p = c(vs[i][j]);
			if (now->to[p] == NULL)
				now->to[p] = new Node();
			now = now->to[p];
			now->v.push_back(q);
		}
	}

	root = new Node();
	for (int i = 1; i <= N; i++) {
		int q = no[i];
		Node *now = root;
		now->v.push_back(q);
		for (auto u : vs[i]) {
			int p = c(u);
			if (now->to[p] == NULL)
				now->to[p] = new Node();
			now = now->to[p];
			now->v.push_back(q);
		}
	}
	root->srt();
	root_rev->srt();

	while (M--) {
		string pref, suff;
		cin >> pref >> suff;
		reverse(suff.begin(), suff.end());

		Node *now = root;
		for (auto u : pref) {
			int q = c(u);
			if (now->to[q] == NULL)
				now->to[q] = new Node();
			now = now->to[q];
		}

		int mn = -1, mx = -1;
		if (now->v.size()) {
			mn = now->v.front();
			mx = now->v.back();
		}

		now = root_rev;
		for (auto u : suff) {
			int q = c(u);
			if (now->to[q] == NULL)
				now->to[q] = new Node();
			now = now->to[q];
		}
		cout << upper_bound(now->v.begin(), now->v.end(), mx) - lower_bound(now->v.begin(), now->v.end(), mn) << "\n";
	}
}

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