제출 #839436

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

selling_rna

// JOIOC 2016, Selling RNA Strands

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

using ii = pair<int, int>;

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

struct Trie{
	Trie* child[4];
	vector<int> nodes;

	Trie() {
		for (int i = 0; i < 4; i++) child[i] = nullptr;
	}

	void add(const string &s, int num, int i = 0){
		if (i >= (int)s.size()){
			nodes.push_back(num);
			return;
		}
		int c = convert(s[i]);
		if (!child[c]) child[c] = new Trie();
		child[c]->add(s, num, i+1);
	}

	void dfs(int &timer, vector<int> &s, vector<ii> &q){
		for (auto node: nodes){
			if (node < 0) q[-node-1].first = timer;
		}
		for (auto node: nodes){
			if (node >= 0) s[node] = timer++;
		}

		for (int c = 0; c < 4; c++){
			if (child[c]) child[c]->dfs(timer, s, q);
		}

		for (auto node: nodes){
			if (node < 0) q[-node-1].second = timer;
		}
	}
};

vector<int> combine(const vector<int> &A, const vector<int> &B){
	int itA = 0, itB = 0;
	vector<int> v;
	while (itA < (int)A.size() && itB < (int)B.size()){
		if (A[itA] < B[itB]){
			v.push_back(A[itA]);
			itA++;
		}
		else{
			v.push_back(B[itB]);
			itB++;
		}
	}
	while (itA < (int)A.size()){
		v.push_back(A[itA]);
		itA++;
	}
	while (itB < (int)B.size()){
		v.push_back(B[itB]);
		itB++;
	}
	return v;
}

int count(vector<int> &V, int L, int R){
	int ansR = upper_bound(V.begin(), V.end(), R) - V.begin();
	int ansL = lower_bound(V.begin(), V.end(), L) - V.begin();
	return ansR - ansL;
}

struct MergeSortTree{
	vector<vector<int>> tree;
	int _n;

	MergeSortTree() {}
	MergeSortTree(int N): tree(4 * N), _n(N) {}
	MergeSortTree(vector<int> &V): MergeSortTree(V.size()) {
		build(1, 0, _n - 1, V);
	}

	void build(int i, int l, int r, vector<int> &V){
		if (l == r) tree[i] = {V[l]};
		else{
			int mid = (l + r) >> 1;
			build(i<<1, l, mid, V);
			build(i<<1|1, mid+1, r, V);
			tree[i] = combine(tree[i<<1], tree[i<<1|1]);
		}
	}

	int get(int tl, int tr, int L, int R) { return get(1, 0, _n - 1, tl, tr, L, R); }
	int get(int i, int l, int r, int tl, int tr, int L, int R){
		if (tl <= l && r <= tr){
			return count(tree[i], L, R);
		}
		if (tl > r || tr < l) return 0;

		int mid = (l + r) >> 1;
		int resx = get(i<<1, l, mid, tl, tr, L, R);
		int resy = get(i<<1|1, mid+1, r, tl, tr, L, R);
		return resx + resy;
	}
};

int n, q;
vector<string> vs;
vector<pair<string, string>> qs;

void main_program(){
	cin >> n >> q;

	vs.resize(n);
	qs.resize(q);

	for (int i = 0; i < n; i++) cin >> vs[i];
	for (int i = 0; i < q; i++) cin >> qs[i].first >> qs[i].second;

	vector<int> idxP(n), idxQ(n);
	vector<ii> qP(q), qQ(q);

	{
		for (auto &s: vs) reverse(s.begin(), s.end());

		Trie root;
		for (int i = 0; i < n; i++){
			root.add(vs[i], i);
		}
		for (int i = 0; i < q; i++){
			string qq = qs[i].second;
			reverse(qq.begin(), qq.end());
			root.add(qq, -i-1);
		}

		int timer = 0;
		root.dfs(timer, idxQ, qQ);
	}
	{
		for (auto &s: vs) reverse(s.begin(), s.end());

		Trie root;
		for (int i = 0; i < n; i++){
			root.add(vs[i], i);
		}
		for (int i = 0; i < q; i++){
			string pp = qs[i].first;
			root.add(pp, -i-1);
		}

		int timer = 0;
		root.dfs(timer, idxP, qP);
	}
	
	vector<int> V(n);
	for (int i = 0; i < n; i++) V[idxP[i]] = idxQ[i];

	MergeSortTree st(V);

	for (int i = 0; i < q; i++){
		if (qP[i].first >= qP[i].second) cout << "0\n";
		else if (qQ[i].first >= qQ[i].second) cout << "0\n";
		else cout << st.get(qP[i].first, qP[i].second - 1, qQ[i].first, qQ[i].second - 1) << "\n";
	}
}

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