oj.uz

Submission #597965

# Submission time Handle Problem Language Result Execution time Memory
597965 2022-07-17T08:42:50 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1061 ms 34116 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;
	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());
	lab.resize(unique(lab.begin(),lab.end()) - lab.begin());
	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);
		}
		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]){
      |           ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 33876 KB Output is correct
2 Correct 368 ms 34068 KB Output is correct
3 Correct 221 ms 33976 KB Output is correct
4 Correct 224 ms 34040 KB Output is correct
5 Correct 169 ms 26552 KB Output is correct
6 Correct 168 ms 26548 KB Output is correct
7 Correct 261 ms 26556 KB Output is correct
8 Correct 267 ms 34116 KB Output is correct
9 Correct 272 ms 33980 KB Output is correct
10 Correct 387 ms 34084 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 5984 KB Output is correct
2 Correct 488 ms 4396 KB Output is correct
3 Correct 678 ms 5344 KB Output is correct
4 Correct 246 ms 4232 KB Output is correct
5 Incorrect 132 ms 4236 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 316 ms 33876 KB Output is correct
9 Correct 368 ms 34068 KB Output is correct
10 Correct 221 ms 33976 KB Output is correct
11 Correct 224 ms 34040 KB Output is correct
12 Correct 169 ms 26552 KB Output is correct
13 Correct 168 ms 26548 KB Output is correct
14 Correct 261 ms 26556 KB Output is correct
15 Correct 267 ms 34116 KB Output is correct
16 Correct 272 ms 33980 KB Output is correct
17 Correct 387 ms 34084 KB Output is correct
18 Correct 1061 ms 5984 KB Output is correct
19 Correct 488 ms 4396 KB Output is correct
20 Correct 678 ms 5344 KB Output is correct
21 Correct 246 ms 4232 KB Output is correct
22 Incorrect 132 ms 4236 KB Output isn't correct
23 Halted 0 ms 0 KB -