Submission #249198

#	Time	Username	Problem	Language	Result	Execution time	Memory
249198		Blagojce	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	993 ms	821916 KiB

selling_rna

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 4e6;
 
const ll A = 911382323;
const ll B = 972663749;

ll modpow(ll x, ll n){
	if(n == 0) return 1%mod;
	ll u = modpow(x, n/2);
	u = (u * u) % mod;
	if(n % 2) u = (u * x) % mod;
	return u;
}
ll inverse(ll x){
	return modpow(x, mod-2);
}
ll add(ll ans, ll val){
	ans = (ans + val) % mod;
	return ans;
}
ll mul(ll ans, ll val){
	ans = (ans * val) % mod;
	return ans;
}
ll sub(ll ans, ll val){
	ans = (ans - val) % mod;
	if(ans < 0) ans += mod;
	return ans;
}
ll _div(ll ans, ll val){
	ans = (ans * inverse(val)) % mod;
	return ans;
}
ll fakt[mxn];
ll bc(ll n, ll k){
	return (fakt[n]*inverse((fakt[k]*fakt[n-k])%mod))%mod;
}
ll sq(ll x){
	return x*x;
}
ll rsum(ll a, ll b){
	return (b-a+1)*(a+b)/2;
}
void prec(){
	fakt[0] = 1;
	fr(i, 1, mxn){
		fakt[i] = mul(fakt[i-1], i);
	}
}


string s[mxn];
int trie[mxn][26];
vector<int> g[mxn];
int TRIESIZE = 1;
void add(int id, string s){
	int u = 0;
	for(auto ch : s){
	
		
		if(trie[u][ch-'A'] == -1){
			trie[u][ch-'A'] = TRIESIZE;
			u = TRIESIZE;
			++TRIESIZE;
		}
		else{
			u = trie[u][ch-'A'];
		}
	}	
	
	g[u].pb(id);
}

int pos[mxn];
int sz[mxn];
int temp_pos = 0;
void dfs(int u){
	pos[u] = temp_pos;
	++temp_pos;
	sz[u] = 1;
	fr(i, 0, 26){
		if(trie[u][i] != -1){
			dfs(trie[u][i]);
			sz[u] += sz[trie[u][i]];
		}
	}
}

vector<pair<ll, ll> > comp;

void hash_prefixes(int i, int p){
	reverse(s[i].begin(), s[i].end());
	ll h = s[i][0];
	comp.pb({h, p});
	fr(j, 1, (int)s[i].size()){
		h = (h * A + s[i][j]) % B;
		comp.pb({h, p});
	}
}
ll fhash(string suf){
	ll h = suf[0];	
	fr(i, 1, (int)suf.size()){
		h = (h * A + suf[i]) % B;
	}
	return h;
}
ll findx(string pre){
	ll u = 0;
	for(auto ch : pre){
		if(trie[u][ch-'A']==-1)return -1;
		u = trie[u][ch-'A'];
	}
	return u;
}
vector<int> v[mxn];


void solve(){
	memset(trie, -1, sizeof(trie));

	int n, m;
	cin >> n >> m;
	fr(i, 0, n){
		cin >> s[i];
		
		add(i, s[i]);
	}
	dfs(0);
	fr(i, 0, TRIESIZE){
		for(auto u : g[i]){
			hash_prefixes(u, pos[i]);
		}
	}
	string pre[m];
	string suf[m];
	ll cval[m];
	fr(i, 0, m){
		cin >> pre[i] >> suf[i]; 
		reverse(suf[i].begin(), suf[i].end());
		ll temp_hash = fhash(suf[i]);
		comp.pb({temp_hash, -(i+1)});
	}
	sort(all(comp));
	ll tval = -1;
	ll bef = -1;
	for(auto u : comp){
		if(u.st != bef){
			++tval;
		}
		if(u.nd < 0){
			cval[-(u.nd+1)] = tval;
			
		}
		else{
				v[tval].pb(u.nd);
		}
		bef = u.st;	
	}
	fr(i, 0, m){
		ll x = findx(pre[i]);
		
		if(x == -1){
			cout<< 0 <<endl;
			continue;
		}
		
		
		ll target_hash = cval[i];
		
		ll le = pos[x];
		ll ri = pos[x] + sz[x];
		
		cout << (lower_bound(all(v[target_hash]), ri) - lower_bound(all(v[target_hash]), le)) << endl;
	}
}
 
int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}	

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