oj.uz

Submission #249198

# Submission time Handle Problem Language Result Execution time Memory
249198 2020-07-14T13:24:19 Z Blagojce Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 993 ms 821916 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 720716 KB Output is correct
2 Correct 355 ms 720504 KB Output is correct
3 Correct 358 ms 720632 KB Output is correct
4 Correct 356 ms 720508 KB Output is correct
5 Correct 354 ms 720504 KB Output is correct
6 Correct 359 ms 720544 KB Output is correct
7 Correct 352 ms 720504 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 821916 KB Output is correct
2 Correct 771 ms 818844 KB Output is correct
3 Correct 819 ms 786768 KB Output is correct
4 Correct 806 ms 785656 KB Output is correct
5 Correct 700 ms 793492 KB Output is correct
6 Correct 698 ms 794648 KB Output is correct
7 Correct 642 ms 764184 KB Output is correct
8 Correct 833 ms 798332 KB Output is correct
9 Correct 811 ms 793244 KB Output is correct
10 Correct 784 ms 787224 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 728552 KB Output is correct
2 Correct 440 ms 725860 KB Output is correct
3 Correct 468 ms 727996 KB Output is correct
4 Correct 440 ms 727436 KB Output is correct
5 Correct 445 ms 725988 KB Output is correct
6 Correct 473 ms 727912 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 720716 KB Output is correct
2 Correct 355 ms 720504 KB Output is correct
3 Correct 358 ms 720632 KB Output is correct
4 Correct 356 ms 720508 KB Output is correct
5 Correct 354 ms 720504 KB Output is correct
6 Correct 359 ms 720544 KB Output is correct
7 Correct 352 ms 720504 KB Output is correct
8 Correct 772 ms 821916 KB Output is correct
9 Correct 771 ms 818844 KB Output is correct
10 Correct 819 ms 786768 KB Output is correct
11 Correct 806 ms 785656 KB Output is correct
12 Correct 700 ms 793492 KB Output is correct
13 Correct 698 ms 794648 KB Output is correct
14 Correct 642 ms 764184 KB Output is correct
15 Correct 833 ms 798332 KB Output is correct
16 Correct 811 ms 793244 KB Output is correct
17 Correct 784 ms 787224 KB Output is correct
18 Correct 486 ms 728552 KB Output is correct
19 Correct 440 ms 725860 KB Output is correct
20 Correct 468 ms 727996 KB Output is correct
21 Correct 440 ms 727436 KB Output is correct
22 Correct 445 ms 725988 KB Output is correct
23 Correct 473 ms 727912 KB Output is correct
24 Correct 843 ms 812700 KB Output is correct
25 Correct 912 ms 816008 KB Output is correct
26 Correct 814 ms 811072 KB Output is correct
27 Correct 857 ms 784664 KB Output is correct
28 Correct 993 ms 802968 KB Output is correct
29 Correct 714 ms 762576 KB Output is correct