oj.uz

Submission #597954

# Submission time Handle Problem Language Result Execution time Memory
597954 2022-07-17T08:32:47 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 19164 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 0 ms 340 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct
6 Correct 0 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 69 ms 18264 KB Output is correct
2 Correct 158 ms 18464 KB Output is correct
3 Correct 94 ms 18380 KB Output is correct
4 Correct 82 ms 18408 KB Output is correct
5 Correct 34 ms 11720 KB Output is correct
6 Correct 36 ms 11916 KB Output is correct
7 Correct 121 ms 13780 KB Output is correct
8 Correct 81 ms 18440 KB Output is correct
9 Correct 87 ms 18428 KB Output is correct
10 Correct 200 ms 18516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 5128 KB Output is correct
2 Correct 459 ms 3600 KB Output is correct
3 Correct 704 ms 4380 KB Output is correct
4 Correct 245 ms 3496 KB Output is correct
5 Correct 132 ms 3644 KB Output is correct
6 Correct 219 ms 4300 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 69 ms 18264 KB Output is correct
9 Correct 158 ms 18464 KB Output is correct
10 Correct 94 ms 18380 KB Output is correct
11 Correct 82 ms 18408 KB Output is correct
12 Correct 34 ms 11720 KB Output is correct
13 Correct 36 ms 11916 KB Output is correct
14 Correct 121 ms 13780 KB Output is correct
15 Correct 81 ms 18440 KB Output is correct
16 Correct 87 ms 18428 KB Output is correct
17 Correct 200 ms 18516 KB Output is correct
18 Correct 1125 ms 5128 KB Output is correct
19 Correct 459 ms 3600 KB Output is correct
20 Correct 704 ms 4380 KB Output is correct
21 Correct 245 ms 3496 KB Output is correct
22 Correct 132 ms 3644 KB Output is correct
23 Correct 219 ms 4300 KB Output is correct
24 Correct 657 ms 18840 KB Output is correct
25 Execution timed out 1578 ms 19164 KB Time limit exceeded
26 Halted 0 ms 0 KB -