Submission #522840

#	Time	Username	Problem	Language	Result	Execution time	Memory
522840		thiago_bastos	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1032 ms	190872 KiB

selling_rna

#include "bits/stdc++.h"
 
using namespace std;
 
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;
 
const int N = 2e6, mod = 1e9 + 9, base = 1845;
 
vector<int> h(string& s) {
	int n = s.size();
	vector<int> a(n + 1);
	i64 k = 1;
	a[0] = 0;
	for(int i = 1; i <= n; ++i) {
		int x0 = a[i - 1];
		int& x1 = a[i];
		k = k * base % mod;
		x1 = (x0 + (s[i - 1] - '0' + 1) * k) % mod;
	}
	a.erase(a.begin());
	return a;
}
 
int t[N][4], nos = 1;
vector<ii> query[N];
unordered_map<int, int> cnt;
vector<int> ans, H[N];
 
void push(string& s) {
	int i = 0;
	for(char ch : s) {
		int& k = t[i][ch - '0'];
		if(k < 0) {
			memset(t[nos], -1, sizeof(t[nos]));
			k = nos++;
		}
		i = k;
	}
	reverse(s.begin(), s.end());
	for(int y : h(s)) H[i].push_back(y);
}
 
void f(string& s) {
	string alpha = "AGCU";
	for(char& ch : s) {
		for(int i = 0; i < 4; ++i) {
			if(ch == alpha[i]) {
				ch = i + '0';
				break;
			}
		}
	}
}
 
void dfs(int u) {	
	for(auto [pos, ht] : query[u]) {
		auto it = cnt.find(ht);
		if(it == cnt.end()) continue;
		ans[pos] -= it->second;
	}

	for(int v = 0; v < 4; ++v) {
		int z = t[u][v];
		if(z < 0) continue;
		dfs(z);
	}

	for(int ht : H[u]) ++cnt[ht];

	for(auto [pos, ht] : query[u]) {
		auto it = cnt.find(ht);
		if(it == cnt.end()) continue;
		ans[pos] += it->second;
	}
}
 
void solve() {
	
	int n, m;
 
	cin >> n >> m;
 
	memset(t[0], -1, sizeof(t[0]));
	ans.assign(m, 0);
 
	for(int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		f(s);
		push(s);
	}
 
	for(int i = 0; i < m; ++i) {
		string a, b;
		int k = 0;
		cin >> a >> b;
		f(a);
		f(b);
		reverse(b.begin(), b.end());
		for(char ch : a) {
			if(t[k][ch - '0'] < 0) {
				k = -1;
				break;
			}
			k = t[k][ch - '0'];
		}
		if(k < 0) continue;
		query[k].emplace_back(i, h(b).back());
	}
 
	dfs(0);
 
	for(int k : ans) cout << k << '\n';
}

int main() {
	int t = 1;
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	// cin >> t;
	while(t--) solve();
}

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