oj.uz

Submission #597926

# Submission time Handle Problem Language Result Execution time Memory
597926 2022-07-17T07:37:29 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 34356 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
int MOD2;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
pii make_hash(string s){
	int n = s.size();
	int z1 = 5;
	int z2 = 5;
	pii hb;
	for(int i=0;i<n;i++){
		int c = 1;
		if(s[i] == 'C')c=2;
		else if(s[i] == 'G')c=3;
		else if(s[i] == 'U')c=4;
		hb.fi += c * 1LL * z1%MOD1;
		hb.se += c * 1LL * z2%MOD2;
		if(hb.fi>=MOD1)hb.fi-=MOD1;
		if(hb.se>=MOD2)hb.se-=MOD2;
		
		z1 = z1 * 1LL * 5 %MOD1;
		z2 = z2 * 1LL * 5 %MOD2;
	}
	return hb;
}
int cmp(string &a,string &b){
	int n = a.size();
	int m = b.size();
	for(int i=0;i<n;i++){
		if(i==m)return 1;//equal
		if(a[i] > b[i])return 0;
		if(b[i] > a[i])return 2;
	}
	return 1;
	
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin>>n>>m;
	MOD2 = uniform_int_distribution<int>(1e8,1e9)(rng);
	vector<string>s(n);
	for(int i=0;i<n;i++)cin>>s[i];
	sort(s.begin(),s.end());
	vector<vector<pii>>ph(n),sh(n); //prefix and suffix hash
	for(int i=0;i<n;i++){
		int k = s[i].size();
		ph[i].resize(k);
		sh[i].resize(k);
		int z1 = 5;
		int z2 = 5;
		pii hb;
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][j] == 'C')c=2;
			else if(s[i][j] == 'G')c=3;
			else if(s[i][j] == 'U')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 5 %MOD1;
			z2 = z2 * 1LL * 5 %MOD2;
			ph[i][j] = hb;
		}
		z1 = 5;
		z2 = 5;
		hb = {0,0};
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][k-j-1] == 'C')c=2;
			else if(s[i][k-j-1] == 'G')c=3;
			else if(s[i][k-j-1] == 'U')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 5 %MOD1;
			z2 = z2 * 1LL * 5 %MOD2;
			sh[i][j] = hb;
		}
	}
	//for(string x:s)cout<<x<<" ";
	//cout<<'\n';
	while(m--){
		
		string p,q;
		cin>>p>>q;
		reverse(q.begin(),q.end());
		pii pre = make_hash(p);
		pii suf = make_hash(q);
		int ans = 0;
		int a = p.size();
		int b = q.size();
		//binary search for borders l and r
		int l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) >= 1)r = mid-1;
			else l=mid+1;
		}//first guy >= p
		int L = l;
		l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) <= 1)l= mid+1;
			else r=mid-1;
			
		}
		int R = r;
		//cout<<L<<" "<<R<<'\n';
		for(int i=L;i<=R;i++){
			if(ph[i][a-1] == pre && sh[i][b-1] == suf)ans++;
			
		}
		cout<<ans<<'\n';
		
	}
	
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 33972 KB Output is correct
2 Correct 289 ms 34268 KB Output is correct
3 Correct 108 ms 34004 KB Output is correct
4 Correct 117 ms 34296 KB Output is correct
5 Correct 60 ms 21588 KB Output is correct
6 Correct 59 ms 21872 KB Output is correct
7 Correct 209 ms 25548 KB Output is correct
8 Correct 121 ms 34356 KB Output is correct
9 Correct 129 ms 34128 KB Output is correct
10 Correct 406 ms 34268 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1572 ms 7660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 142 ms 33972 KB Output is correct
9 Correct 289 ms 34268 KB Output is correct
10 Correct 108 ms 34004 KB Output is correct
11 Correct 117 ms 34296 KB Output is correct
12 Correct 60 ms 21588 KB Output is correct
13 Correct 59 ms 21872 KB Output is correct
14 Correct 209 ms 25548 KB Output is correct
15 Correct 121 ms 34356 KB Output is correct
16 Correct 129 ms 34128 KB Output is correct
17 Correct 406 ms 34268 KB Output is correct
18 Execution timed out 1572 ms 7660 KB Time limit exceeded
19 Halted 0 ms 0 KB -