oj.uz

Submission #597978

# Submission time Handle Problem Language Result Execution time Memory
597978 2022-07-17T08:50:10 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 35280 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;
		}
	}
	for(int i=0;i<n;i++){
		for(pii x:sh[i])lab.push_back(x);
		
	}
	sort(lab.begin(),lab.end());
	lab.resize(unique(lab.begin(),lab.end()) - lab.begin());
	//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]){
			int y = lower_bound(lab.begin(),lab.end(),x) - lab.begin();
			//prev = upd(prev,y,0,lab.size()-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:117:8: warning: unused variable 'y' [-Wunused-variable]
  117 |    int y = lower_bound(lab.begin(),lab.end(),x) - lab.begin();
      |        ^

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 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 286 ms 34740 KB Output is correct
2 Correct 377 ms 34868 KB Output is correct
3 Correct 252 ms 34824 KB Output is correct
4 Correct 244 ms 34868 KB Output is correct
5 Correct 161 ms 28248 KB Output is correct
6 Correct 161 ms 28408 KB Output is correct
7 Correct 249 ms 30204 KB Output is correct
8 Correct 297 ms 34940 KB Output is correct
9 Correct 268 ms 34900 KB Output is correct
10 Correct 417 ms 34992 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 5980 KB Output is correct
2 Correct 479 ms 4452 KB Output is correct
3 Correct 758 ms 5196 KB Output is correct
4 Correct 257 ms 4332 KB Output is correct
5 Correct 151 ms 4436 KB Output is correct
6 Correct 273 ms 5196 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 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 286 ms 34740 KB Output is correct
9 Correct 377 ms 34868 KB Output is correct
10 Correct 252 ms 34824 KB Output is correct
11 Correct 244 ms 34868 KB Output is correct
12 Correct 161 ms 28248 KB Output is correct
13 Correct 161 ms 28408 KB Output is correct
14 Correct 249 ms 30204 KB Output is correct
15 Correct 297 ms 34940 KB Output is correct
16 Correct 268 ms 34900 KB Output is correct
17 Correct 417 ms 34992 KB Output is correct
18 Correct 1083 ms 5980 KB Output is correct
19 Correct 479 ms 4452 KB Output is correct
20 Correct 758 ms 5196 KB Output is correct
21 Correct 257 ms 4332 KB Output is correct
22 Correct 151 ms 4436 KB Output is correct
23 Correct 273 ms 5196 KB Output is correct
24 Correct 1002 ms 35244 KB Output is correct
25 Execution timed out 1577 ms 35280 KB Time limit exceeded
26 Halted 0 ms 0 KB -