Submission #1253341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253341		pasta	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	319 ms	205364 KiB

selling_rna

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

//typedef long long ll;
//#define lc (id * 2)
//#define rc (lc + 1)
//#define int long long
#define all(x)	x.begin(), x.end()
#define pb	push_back
const int maxn = 2e6 + 10;
const int LOG = 33;

vector<int> mem[maxn];
string S[maxn];
int n, q, trieVt[2], nxt[2][maxn][4], l[maxn], r[maxn];
map<int, int> mp;

void add(int tp, int i, string s) {
	if (tp)
		reverse(all(s));
	
	int cur = 0;
	for (char chil : s) {
		char c = mp[chil];
		if (!nxt[tp][cur][c])
			nxt[tp][cur][c] = ++trieVt[tp];
		
		cur = nxt[tp][cur][c];
		
		if (tp)
			mem[cur].pb(i);
		else {
			if (!l[cur])
				l[cur] = i;
			r[cur] = i;
		}
	}
}


int get(string s, int tp) {
	if (tp)
		reverse(all(s));
	
	int cur = 0;
	for (char chil : s) {
		char c = mp[chil];
		if (!nxt[tp][cur][c])
			return 0;
		cur = nxt[tp][cur][c];
	}		
	return cur;
}



int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> S[i];
	
	mp['A'] = 0;
	mp['G'] = 1;
	mp['C'] = 2;
	mp['U'] = 3;
	sort(S + 1, S + n + 1);
	for (int i = 1; i <= n; i++) {
		add(1, i, S[i]);
		add(0, i, S[i]);
	}
	while (q--) {
		string P, Q;
		cin >> P >> Q;
		
		int v = get(P, 0);
		int u = get(Q, 1);
		
		if (!u || !v) {
			cout << 0 << '\n';
			continue;
		}
		
		
		int pf1 = upper_bound(all(mem[u]), r[v]) - mem[u].begin();
		int pf2 = lower_bound(all(mem[u]), l[v]) - mem[u].begin();
		cout << pf1 - pf2 << '\n';
	}
	return 0;
}

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