Submission #26513

#	Time	Username	Problem	Language	Result	Execution time	Memory
26513		rubabredwan	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	559 ms	849740 KiB

selling_rna

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int M = 2000005;

int mp[M], from[M];

struct TRIE{

	map <char, int> trie[M];
	int in[M], out[M], cnt[M];
	int idx, t;

	void init(){
		memset(cnt, 0, sizeof(cnt));
		idx = 1;
		t = 0;
	}

	int insert(string str, int ot){
		int cur = 1;
		for(auto c : str){
			if(trie[cur].count(c) == 0) trie[cur][c] = ++idx;
			cur = trie[cur][c];
		}
		from[cur] = ot;
		++cnt[cur];
		return cur;
	}

	int query(string str){
		int cur = 1;
		for(auto c : str){
			if(trie[cur].count(c) == 0) return -1;
			cur = trie[cur][c];
		}
		return cur;
	}

	void dfs(int at){
		in[at] = ++t;
		mp[t] = at;
		for(auto c : {'A', 'C', 'G', 'U'}){
			if(trie[at].count(c)){ 
				dfs(trie[at][c]);
			}
		}
		out[at] = t;
	}

};

int n, m, k;
int nn, mm;
string rna[N];
TRIE t1, t2;
int id1[N], id2[N];

int root[M];
int lf[20 * M], rf[20 * M];
int sum[20 * M];
int idx;

int update(int b, int e, int node, int pos, int val){
	int cur = ++idx;
	sum[cur] = sum[node] + val;
	if(b == e) return cur;
	int mid = (b + e) / 2;
	lf[cur] = lf[node];
	rf[cur] = rf[node];
	if(pos <= mid) lf[cur] = update(b, mid, lf[node], pos, val);
	else rf[cur] = update(mid + 1, e, rf[node], pos, val);
	return cur;
}

int get(int b, int e, int node, int x, int y){
	if(y < b || e < x || node == 0) return 0;
	if(b >= x && e <= y) return sum[node];
	int mid = (b + e) / 2;
	return get(b, mid, lf[node], x, y) + get(mid + 1, e, rf[node], x, y);
}

void init(){
	t1.init();
	for(int i = 1; i <= n; ++i){
		id1[i] = t1.insert(rna[i], 0);
	}	
	t1.dfs(1);
	nn = t1.idx;
	for(int i = 1; i <= n; ++i) reverse(rna[i].begin(), rna[i].end());
	for(int i = 1; i <= n; ++i){
		id2[i] = t2.insert(rna[i], t1.in[ id1[i] ]);
	}	
	t2.dfs(1);
	mm = t2.idx;
	for(int i = 1; i <= mm; ++i){
		int at = mp[i];
		if(from[at] == 0) root[i] = root[i-1];
		else{
			root[i] = update(1, nn, root[i-1], from[at], t2.cnt[at]);
		}
	}
}

int query(string p, string q){
	int a = t1.query(p);
	int b = t2.query(q);
	if(a == -1 || b == -1) return 0;
	int aa = get(1, nn, root[ t2.out[b] ], t1.in[a], t1.out[a]);
	int bb = get(1, nn, root[ t2.in[b] - 1 ], t1.in[a], t1.out[a]);
	return aa - bb;
}

int main(){
	ios_base::sync_with_stdio(false);
	t1.init();
	t2.init();
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		cin >> rna[i];
	}
	init();
	string p, q;
	for(int i = 1; i <= m; ++i){
		cin >> p >> q;
		reverse(q.begin(), q.end());
		cout << query(p, q) << '\n';
	}
	return 0;
}

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