oj.uz

Submission #597959

# Submission time Handle Problem Language Result Execution time Memory
597959 2022-07-17T08:37:49 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1163 ms 34136 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
	vector<pii>lab;
	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;
			lab.push_back(hb);
		}
	}
	sort(lab.begin(),lab.end());
	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:111:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  111 |   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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 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 338 ms 33912 KB Output is correct
2 Correct 457 ms 34116 KB Output is correct
3 Correct 245 ms 33940 KB Output is correct
4 Correct 246 ms 34136 KB Output is correct
5 Correct 191 ms 26496 KB Output is correct
6 Correct 207 ms 26504 KB Output is correct
7 Correct 293 ms 26552 KB Output is correct
8 Correct 304 ms 34108 KB Output is correct
9 Correct 306 ms 33988 KB Output is correct
10 Correct 453 ms 34124 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 5908 KB Output is correct
2 Correct 491 ms 4316 KB Output is correct
3 Correct 771 ms 5168 KB Output is correct
4 Correct 269 ms 4244 KB Output is correct
5 Incorrect 148 ms 4312 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 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 338 ms 33912 KB Output is correct
9 Correct 457 ms 34116 KB Output is correct
10 Correct 245 ms 33940 KB Output is correct
11 Correct 246 ms 34136 KB Output is correct
12 Correct 191 ms 26496 KB Output is correct
13 Correct 207 ms 26504 KB Output is correct
14 Correct 293 ms 26552 KB Output is correct
15 Correct 304 ms 34108 KB Output is correct
16 Correct 306 ms 33988 KB Output is correct
17 Correct 453 ms 34124 KB Output is correct
18 Correct 1163 ms 5908 KB Output is correct
19 Correct 491 ms 4316 KB Output is correct
20 Correct 771 ms 5168 KB Output is correct
21 Correct 269 ms 4244 KB Output is correct
22 Incorrect 148 ms 4312 KB Output isn't correct
23 Halted 0 ms 0 KB -