Submission #1083717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083717		idiotcomputer	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	252 ms	229212 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define sz(x) (int) x.size()
#define pb push_back

const int mxN = 1e5+5;
const int mC = 2e6+5;
int n;

int v[mC];
vector<int> idxs[mC];
vector<int> adj[mC];
int cnt = 0;

int dfs(int node, int l, int r, int idx, string &s){
	if (idx == 0){
		return lower_bound(idxs[node].begin(), idxs[node].end(),r) - lower_bound(idxs[node].begin(),idxs[node].end(),l);
	}
	for (int i : adj[node]){
		if (v[i] == s[idx-1]-'A') return dfs(i,l,r,idx-1,s);
	}
	return 0;
}

void add(int node, int cidx, int idx, string &s){
	idxs[node].pb(cidx);
	if (idx == 0) return;
	for (int i : adj[node]){
		if (v[i] == s[idx-1]-'A') return add(i,cidx,idx-1,s);
	}
	v[cnt] = s[idx-1] - 'A';
	adj[node].pb(cnt);
	cnt++;
	return add(cnt-1,cidx,idx-1,s);
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int m;
	cin >> n >> m;

	vector<string> all(n);
	for (int i = 0; i < n; i++) cin >> all[i];
	sort(all.begin(),all.end());

	string temp;
	v[0] = 1;
	cnt++;
	for (int i = 0; i < n; i++){
		temp = all[i]+'B';
		add(0,i,sz(temp)-1,temp);
	} 
	

	int l,r;
	string a,b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		l = lower_bound(all.begin(),all.end(), a) - all.begin();
		r = lower_bound(all.begin(),all.end(), a+'Z') - all.begin();
		temp = b + 'B';
		cout << dfs(0,l,r,sz(temp)-1,temp) << '\n';
	}
	return 0;
}

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