oj.uz

Submission #947419

# Submission time Handle Problem Language Result Execution time Memory
947419 2024-03-16T06:56:45 Z pcc Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 320276 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mod = 712271227;
const int p = 7;

const int mxn = 1e5+10;
const int mxm = 2e6+10;
const int B = 64;

int pw[mxm];
basic_string<int> base[mxn];
basic_string<int> pref[mxn];
basic_string<int> suf[mxn];
pair<string,string> req[mxn];
pii qhash[mxn];
int N,Q;
int ans[mxn];
basic_string<ll> prec[B+1][B+1];
vector<pii> vs;

inline int mad(int a,int b){
	a += b;
	return a>=mod?a-mod:a;
}
inline int mub(int a,int b){
	return mad(a,mod-b);
}

inline int mul(int a,int b){
	return 1ll*a*b%mod;
}

void process(int id){
	auto &s = base[id];
	int n = s.size();
	pref[id] = suf[id] = basic_string<int>(n,0);
	pref[id][0] = suf[id].back() = 0;
	for(int i = 0;i<n;i++){
		if(i){
			pref[id][i] = pref[id][i-1];
			suf[id][n-1-i] = suf[id][n-1-i+1];
		}
		pref[id][i] = mad(pref[id][i],mul(s[i],pw[i]));
		suf[id][n-1-i] = mad(suf[id][n-1-i],mul(s[n-1-i],pw[i]));
	}
	int lim = min(B,n);
	for(int i = 1;i<=lim;i++){
		for(int j = 1;j<=lim;j++){
			ll val = 1ll*pref[id][i-1]*mod+suf[id][n-j];
			prec[i][j] += val;
		}
	}
	return;
}

void makereq(int id){
	auto &[l,r] = req[id];
	int n = l.size();
	for(int i = 0;i<n;i++){
		qhash[id].fs = mad(qhash[id].fs,mul(l[i],pw[i]));
	}
	n = r.size();
	for(int i = n-1;i>=0;i--){
		qhash[id].sc = mad(qhash[id].sc,mul(r[i],pw[n-1-i]));
	}
	return;
}

void big(int ls,int rs,int lh,int rh){
	int b = max(ls,rs);
	auto pos = lower_bound(vs.begin(),vs.end(),pii(max(ls,rs),-1))-vs.begin();
	int ans = 0;
	for(int i = pos;i<vs.size();i++){
		int now = vs[i].sc;
		int n = base[now].size();
		if(n<max(ls,rs))continue;
		if(pref[now][ls-1] == lh&&suf[now][n-rs] == rh)ans++;
	}
	cout<<ans<<'\n';
	return;
}

void small(int ls,int rs,int lh,int rh){
	ll tar = 1ll*lh*mod+rh;
	auto lp = lower_bound(prec[ls][rs].begin(),prec[ls][rs].end(),tar)-prec[ls][rs].begin();
	auto rp = upper_bound(prec[ls][rs].begin(),prec[ls][rs].end(),tar)-prec[ls][rs].begin();
	cout<<(rp-lp)<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	pw[0] = 1;
	for(int i = 1;i<mxn;i++)pw[i] = mul(pw[i-1],p);
	for(int i = 1;i<=N;i++){
		string s1;
		cin>>s1;
		for(auto &j:s1){
			int tmp;
			if(j == 'A')tmp = 1;
			else if(j == 'C')tmp = 2;
			else if(j == 'G')tmp = 3;
			else tmp = 4;
			base[i] += tmp;
		}
		vs.push_back(pii((int)base[i].size(),i));
		process(i);
	}
	for(int i = 1;i<=Q;i++){
		string s1,s2;
		cin>>s1>>s2;
		for(auto &j:s1){
			int tmp;
			if(j == 'A')tmp = 1;
			else if(j == 'C')tmp = 2;
			else if(j == 'G')tmp = 3;
			else tmp = 4;
			req[i].fs += tmp;
		}
		for(auto &j:s2){
			int tmp;
			if(j == 'A')tmp = 1;
			else if(j == 'C')tmp = 2;
			else if(j == 'G')tmp = 3;
			else tmp = 4;
			req[i].sc += tmp;
		}
		makereq(i);
	}


	sort(vs.begin(),vs.end());
	for(int i = 1;i<=B;i++)for(int j = 1;j<=B;j++)sort(prec[i][j].begin(),prec[i][j].end());
	for(int i = 1;i<=Q;i++){
		auto &[l,r] = req[i];
		if(l.size()>B||r.size()>B)big(l.size(),r.size(),qhash[i].fs,qhash[i].sc);
		else small(l.size(),r.size(),qhash[i].fs,qhash[i].sc);
	}
}

Compilation message

selling_rna.cpp: In function 'void big(int, int, int, int)':
selling_rna.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = pos;i<vs.size();i++){
      |                  ~^~~~~~~~~~
selling_rna.cpp:81:6: warning: unused variable 'b' [-Wunused-variable]
   81 |  int b = max(ls,rs);
      |      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 114144 KB Output is correct
2 Correct 1084 ms 205360 KB Output is correct
3 Correct 680 ms 169696 KB Output is correct
4 Correct 1051 ms 215128 KB Output is correct
5 Correct 1195 ms 252144 KB Output is correct
6 Correct 1237 ms 252500 KB Output is correct
7 Correct 228 ms 115792 KB Output is correct
8 Correct 935 ms 280572 KB Output is correct
9 Correct 869 ms 280552 KB Output is correct
10 Correct 716 ms 275284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 21432 KB Output is correct
2 Correct 47 ms 27616 KB Output is correct
3 Correct 42 ms 25428 KB Output is correct
4 Correct 24 ms 22320 KB Output is correct
5 Correct 46 ms 27620 KB Output is correct
6 Correct 42 ms 25428 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 18900 KB Output is correct
6 Correct 5 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 432 ms 114144 KB Output is correct
9 Correct 1084 ms 205360 KB Output is correct
10 Correct 680 ms 169696 KB Output is correct
11 Correct 1051 ms 215128 KB Output is correct
12 Correct 1195 ms 252144 KB Output is correct
13 Correct 1237 ms 252500 KB Output is correct
14 Correct 228 ms 115792 KB Output is correct
15 Correct 935 ms 280572 KB Output is correct
16 Correct 869 ms 280552 KB Output is correct
17 Correct 716 ms 275284 KB Output is correct
18 Correct 25 ms 21432 KB Output is correct
19 Correct 47 ms 27616 KB Output is correct
20 Correct 42 ms 25428 KB Output is correct
21 Correct 24 ms 22320 KB Output is correct
22 Correct 46 ms 27620 KB Output is correct
23 Correct 42 ms 25428 KB Output is correct
24 Execution timed out 1583 ms 320276 KB Time limit exceeded
25 Halted 0 ms 0 KB -