제출 #681711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681711		NK_	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	535 ms	426312 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int K = 4;
const int MX = 2e6 + 10;

struct node {
	vector<int> nxt, who;
	int sz;

	node() { nxt = vector<int>(K, -1); who = {}; sz = 0; }
};

template<int MX> struct Trie {
	int cur = 1;
	node T[MX];

	void add(const string &S, int IDX) {
		int v = 0;
		for(auto c : S) {
			if (T[v].nxt[c-'A'] == -1) {
				T[v].nxt[c-'A'] = cur++; 
			}
			T[v].sz++;
			T[v].who.push_back(IDX);

			v = T[v].nxt[c-'A'];
		}

		T[v].sz++;
		T[v].who.push_back(IDX);
	}

	array<int, 2> query(const string &S) {
		int v = 0;
		for(auto c : S) {
			if (T[v].nxt[c-'A'] == -1) return {-1, -1};
			v = T[v].nxt[c-'A'];
		}
		return {T[v].who.front(), T[v].who.back()};
	}

	int query(const string &S, int L, int R) {
		int v = 0; 
		for(auto c : S) {
			if (T[v].nxt[c-'A'] == -1) return 0;
			v = T[v].nxt[c-'A'];
		}
		return int(upper_bound(begin(T[v].who), end(T[v].who), R) - lower_bound(begin(T[v].who), end(T[v].who), L));
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	Trie<MX> pfx, sfx;

	auto alter = [&](string &S) {
		for(auto &c : S) {
			if (c == 'U') c = 'D';
			if (c == 'G') c = 'B';
		}
	};

	int N, Q; cin >> N >> Q;
	vector<string> A;
	for(int i = 0; i < N; i++) {
		string s; cin >> s; alter(s);
		A.push_back(s);
	}

	sort(begin(A), end(A));

	for(int i = 0; i < N; i++) {
		pfx.add(A[i], i);
		reverse(begin(A[i]), end(A[i]));
		sfx.add(A[i], i);
	}

	while(Q--) {
		string p, s; cin >> p >> s; alter(p); alter(s);
		reverse(begin(s), end(s));
		auto [L, R] = pfx.query(p);
		cout << sfx.query(s, L, R) << nl;
	}



    return 0;
}

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