oj.uz

답안 #839436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839436 2023-08-30T03:08:35 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 229 ms 162508 KB 
// 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 131372 KB Output is correct
2 Correct 141 ms 127268 KB Output is correct
3 Correct 142 ms 131536 KB Output is correct
4 Correct 139 ms 126172 KB Output is correct
5 Correct 174 ms 160116 KB Output is correct
6 Correct 177 ms 162508 KB Output is correct
7 Correct 34 ms 12580 KB Output is correct
8 Correct 118 ms 103716 KB Output is correct
9 Correct 110 ms 89404 KB Output is correct
10 Correct 85 ms 82160 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 18568 KB Output is correct
2 Correct 34 ms 11340 KB Output is correct
3 Correct 41 ms 15572 KB Output is correct
4 Correct 27 ms 12880 KB Output is correct
5 Correct 28 ms 11348 KB Output is correct
6 Correct 37 ms 15568 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 138 ms 131372 KB Output is correct
9 Correct 141 ms 127268 KB Output is correct
10 Correct 142 ms 131536 KB Output is correct
11 Correct 139 ms 126172 KB Output is correct
12 Correct 174 ms 160116 KB Output is correct
13 Correct 177 ms 162508 KB Output is correct
14 Correct 34 ms 12580 KB Output is correct
15 Correct 118 ms 103716 KB Output is correct
16 Correct 110 ms 89404 KB Output is correct
17 Correct 85 ms 82160 KB Output is correct
18 Correct 37 ms 18568 KB Output is correct
19 Correct 34 ms 11340 KB Output is correct
20 Correct 41 ms 15572 KB Output is correct
21 Correct 27 ms 12880 KB Output is correct
22 Correct 28 ms 11348 KB Output is correct
23 Correct 37 ms 15568 KB Output is correct
24 Correct 145 ms 114364 KB Output is correct
25 Correct 175 ms 117540 KB Output is correct
26 Correct 134 ms 111948 KB Output is correct
27 Correct 134 ms 112876 KB Output is correct
28 Correct 229 ms 60728 KB Output is correct
29 Correct 100 ms 40528 KB Output is correct