Submission #343296

#	Time	Username	Problem	Language	Result	Execution time	Memory
343296		Millad	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1569 ms	40556 KiB

selling_rna

// In the name of god
#include <bits/stdc++.h>
 
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;
 
const ll maxn = 1e5 + 6, inf = 1e18, mod = 1e9 + 7, mod2 = 1e9 + 9;
ll n, m, pw26[2][maxn];
str s[maxn], t[maxn];
vector <int> v[2][maxn];
void hAsh(int k){
	int sz = s[k].size();
	for(int i = 0; i < sz; i ++){
		ll c = s[k][i] - 'A';
		v[0][k].pb(c * pw26[0][i] % mod);
		v[1][k].pb(c * pw26[1][i] % mod2);
		if(i > 0)(v[0][k][i] += v[0][k][i - 1]) %= mod;
		if(i > 0)(v[1][k][i] += v[1][k][i - 1]) %= mod2;
	}
}
pll HASH(int k){
	int sz = t[k].size();
	ll x = 0, x2 = 0;
	for(int i = 0; i < sz; i ++){
		ll c = t[k][i] - 'A';
		(x += c * pw26[0][i] % mod) %= mod;
		(x2 += c * pw26[1][i] % mod2) %= mod2;
	}
	pll pr = {x, x2};
	return pr;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	pw26[0][0] = 1;
	pw26[1][0] = 1;
	ll z = 26;
	for(int i = 1; i < maxn; i ++){
		pw26[0][i] = (pw26[0][i - 1] * z % mod);
		pw26[1][i] = (pw26[1][i - 1] * z % mod2);
	}
	cin >> n >> m;
	for(int i = 0; i < n; i ++){
		cin >> s[i];
		hAsh(i);
	}
	for(int i = 0; i < m; i ++){
		cin >> t[i * 2] >> t[i * 2 + 1];
		pll p1 = HASH(i * 2);
		pll p2 = HASH(i * 2 + 1);
		ll ans = 0;
		for(int j = 0; j < n; j ++){
			if(s[j].size() < t[i * 2].size())continue;
			if(s[j].size() < t[i * 2 + 1].size())continue;
			if(v[0][j][t[i * 2].size() - 1] != p1.F)continue;
			if(v[1][j][t[i * 2].size() - 1] != p1.S)continue;
			ll x = v[0][j][s[j].size() - 1];
			int szj = s[j].size();
			int szq = t[i * 2 + 1].size();
			int dif = szj;
			dif -= szq;
			if(dif)x = (x - v[0][j][dif - 1] + mod) % mod;
         if((p2.F * pw26[0][dif] % mod) != x)continue;
			x = v[1][j][s[j].size() - 1];
			if(dif)x = (x - v[1][j][dif - 1] + mod2) % mod2;
			if((p2.S * pw26[1][dif] % mod2) != x)continue;
			ans ++;
		}
		cout << ans << "\n";
	}
}

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