oj.uz

Submission #597963

# Submission time Handle Problem Language Result Execution time Memory
597963 2022-07-17T08:40:56 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 19668 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 = {0,0};
	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 2;
		if(b[i] > a[i])return 0; //a is smaller 
		if(a[i] > b[i])return 2; //a is bigger
	}
	return 1;
}
const int segsz = 2e7;
int ndcnt = 0;
int cnt[segsz];
int ch[2][segsz];
int upd(int v,int pos,int l,int r){
	int nw = ++ndcnt;
	if(l==r){
		cnt[nw] = cnt[v]+1;
		return nw;
	}
	int tm = (l+r)/2;
	cnt[nw] = cnt[v]+1;
	if(pos<=tm){
		if(!ch[0][v])ch[0][v] = ++ndcnt;
		ch[1][nw] = ch[1][v];
		ch[0][nw] = upd(ch[0][v],pos,l,tm);
	}
	else{
		if(!ch[1][v])ch[1][v] = ++ndcnt;
		ch[0][nw] = ch[0][v];
		ch[1][nw] = upd(ch[1][v],pos,tm+1,r);
	}
	return nw;
}
int query(int v,int l,int r,int pos){
	//cout<<l<<" "<<r<<" "<<cnt[v]<<'\n';
	if(!v)return 0;
	if(l==r)return cnt[v];
	int tm = (l+r)/2;
	if(pos<=tm)return query(ch[0][v],l,tm,pos);
	else return query(ch[1][v],tm+1,r,pos);
	
}
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>>sh(n); //prefix and suffix hash
	map<pii,int>labels;
	int labelnum = 0;
	for(int i=0;i<n;i++){
		int k = s[i].size();
		sh[i].resize(k);
		int z1 = 5;
		int z2 = 5;
		pii 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(pii x:sh[i]){
			//if(labels.find(x) == labels.end())labels[x] = labelnum++;
		}
	}
	vector<int>root(n);
	int prev = 0;
	for(int i=0;i<n;i++){
		//cout<<i<<'\n';
		for(pii x:sh[i]){
			//prev = upd(prev,labels[x],0,labelnum-1);
			//for(int i=0;i<labelnum;i++)cout<<query(prev,0,labelnum-1,i)<<" ";
			//cout<<'\n';
		}
		root[i] = prev;
	}
	while(m--){
		
		string p,q;
		cin>>p>>q;
		reverse(q.begin(),q.end());
		pii suf = make_hash(q);
		int ans = 0;
		//binary search for borders l and r
		/*
			cout<<"comps"<<'\n';
			for(int i=0;i<n;i++)cout<<cmp(p,s[i])<<" ";
			cout<<'\n';
		*/
		//this is 2222211111000000 finding a range of 11111111
		int l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) <=1 )r = mid-1; //p >= s[mid];
			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; //p <= s[mid]
			else r=mid-1;
			
		}
		int R = r;
		//last guy <= p
		//cout<<L<<" "<<R<<'\n';
		if(R>=L){
			//cout<<labels[suf]<<" "<<L<<" "<<R<<'\n';
			int b = q.length();
			for(int i=L;i<=R;i++)if(sh[i][b-1] == suf)ans++;
			//ans+=query(root[R],0,labelnum-1,labels[suf]);
			//if(L)ans-=query(root[L-1],0,labelnum-1,labels[suf]);
		}
		
		cout<<ans<<'\n';
		
	}
	
	
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:104:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  104 |   for(pii x:sh[i]){
      |           ^
selling_rna.cpp:112:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  112 |   for(pii x:sh[i]){
      |           ^
selling_rna.cpp:83:6: warning: unused variable 'labelnum' [-Wunused-variable]
   83 |  int labelnum = 0;
      |      ^~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 18256 KB Output is correct
2 Correct 153 ms 18576 KB Output is correct
3 Correct 76 ms 18320 KB Output is correct
4 Correct 84 ms 18484 KB Output is correct
5 Correct 36 ms 11664 KB Output is correct
6 Correct 34 ms 11928 KB Output is correct
7 Correct 127 ms 13780 KB Output is correct
8 Correct 80 ms 18360 KB Output is correct
9 Correct 80 ms 18388 KB Output is correct
10 Correct 233 ms 18424 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 5196 KB Output is correct
2 Correct 498 ms 3636 KB Output is correct
3 Correct 725 ms 4512 KB Output is correct
4 Correct 264 ms 3488 KB Output is correct
5 Correct 154 ms 3516 KB Output is correct
6 Correct 223 ms 4684 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 81 ms 18256 KB Output is correct
9 Correct 153 ms 18576 KB Output is correct
10 Correct 76 ms 18320 KB Output is correct
11 Correct 84 ms 18484 KB Output is correct
12 Correct 36 ms 11664 KB Output is correct
13 Correct 34 ms 11928 KB Output is correct
14 Correct 127 ms 13780 KB Output is correct
15 Correct 80 ms 18360 KB Output is correct
16 Correct 80 ms 18388 KB Output is correct
17 Correct 233 ms 18424 KB Output is correct
18 Correct 1074 ms 5196 KB Output is correct
19 Correct 498 ms 3636 KB Output is correct
20 Correct 725 ms 4512 KB Output is correct
21 Correct 264 ms 3488 KB Output is correct
22 Correct 154 ms 3516 KB Output is correct
23 Correct 223 ms 4684 KB Output is correct
24 Correct 744 ms 19388 KB Output is correct
25 Execution timed out 1564 ms 19668 KB Time limit exceeded
26 Halted 0 ms 0 KB -