oj.uz

Submission #598001

# Submission time Handle Problem Language Result Execution time Memory
598001 2022-07-17T09:13:27 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 18972 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
const int MOD2 = 998244353;
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){
	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;
	vector<string>s(n);
	for(int i=0;i<n;i++)cin>>s[i];
	sort(s.begin(),s.end());
	vector<vector<pii>>sh(n);
	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;
		}
	}
	while(m--){
		
		string p,q;
		cin>>p>>q;
		reverse(q.begin(),q.end());
		pii suf = make_hash(q);
		int ans = 0;

		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;
		if(R>=L){
			int b = q.length();
			for(int i=L;i<=R;i++)if(sh[i][b-1] == suf)ans++;
		}
		
		cout<<ans<<'\n';
		
	}
	
	
}

Compilation message

selling_rna.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
selling_rna.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 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 77 ms 18248 KB Output is correct
2 Correct 135 ms 18424 KB Output is correct
3 Correct 64 ms 18340 KB Output is correct
4 Correct 82 ms 18576 KB Output is correct
5 Correct 38 ms 11640 KB Output is correct
6 Correct 37 ms 11880 KB Output is correct
7 Correct 118 ms 13800 KB Output is correct
8 Correct 67 ms 18380 KB Output is correct
9 Correct 70 ms 18452 KB Output is correct
10 Correct 237 ms 18540 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 4860 KB Output is correct
2 Correct 444 ms 3536 KB Output is correct
3 Correct 721 ms 4304 KB Output is correct
4 Correct 276 ms 3492 KB Output is correct
5 Correct 134 ms 3396 KB Output is correct
6 Correct 248 ms 4164 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 77 ms 18248 KB Output is correct
9 Correct 135 ms 18424 KB Output is correct
10 Correct 64 ms 18340 KB Output is correct
11 Correct 82 ms 18576 KB Output is correct
12 Correct 38 ms 11640 KB Output is correct
13 Correct 37 ms 11880 KB Output is correct
14 Correct 118 ms 13800 KB Output is correct
15 Correct 67 ms 18380 KB Output is correct
16 Correct 70 ms 18452 KB Output is correct
17 Correct 237 ms 18540 KB Output is correct
18 Correct 1102 ms 4860 KB Output is correct
19 Correct 444 ms 3536 KB Output is correct
20 Correct 721 ms 4304 KB Output is correct
21 Correct 276 ms 3492 KB Output is correct
22 Correct 134 ms 3396 KB Output is correct
23 Correct 248 ms 4164 KB Output is correct
24 Correct 722 ms 18972 KB Output is correct
25 Execution timed out 1598 ms 18884 KB Time limit exceeded
26 Halted 0 ms 0 KB -