oj.uz

Submission #254663

# Submission time Handle Problem Language Result Execution time Memory
254663 2020-07-30T12:12:49 Z alishahali1382 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 190 ms 53496 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, SGM=4;

map<char, int> mp={{'A', 0}, {'U', 1}, {'C', 2}, {'G', 3}};
int n, m, k, u, v, x, y, t, a, b;
int TR[2000001][5], ts;
int ans[MAXN];
string S[MAXN], P, Q[MAXN];
vector<int> vec[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=n; i++) cin>>S[i];
	sort(S+1, S+n+1);
	for (int i=1; i<=m; i++){
		cin>>P>>Q[i];
		int l=lower_bound(S+1, S+n+1, P)-S;
		int r=upper_bound(S+l, S+n+1, P+'Z')-S;
		if (l==r) continue ;
		reverse(all(Q[i]));
		vec[l-1].pb(-i);
		vec[r-1].pb(+i);
	}
	for (int i=1; i<=n; i++){
		reverse(all(S[i]));
		int v=0;
		for (char ch:S[i]){
			int c=mp[ch];
			if (!TR[v][c]) TR[v][c]=++ts;
			v=TR[v][c];
			TR[v][4]++;
		}
		for (int x:vec[i]){
			int id=abs(x), z=id/x;
			int v=0;
			for (char ch:Q[id]){
				int c=mp[ch];
				v=TR[v][c];
				if (!v) break ;
			}
			ans[id]+=z*TR[v][4];
		}
	}
	for (int i=1; i<=m; i++) cout<<ans[i]<<"\n";
	
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 53496 KB Output is correct
2 Correct 78 ms 51448 KB Output is correct
3 Correct 95 ms 17396 KB Output is correct
4 Correct 103 ms 17272 KB Output is correct
5 Correct 77 ms 37368 KB Output is correct
6 Correct 85 ms 37752 KB Output is correct
7 Correct 61 ms 18168 KB Output is correct
8 Correct 95 ms 33016 KB Output is correct
9 Correct 78 ms 30840 KB Output is correct
10 Correct 53 ms 26616 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10552 KB Output is correct
2 Correct 35 ms 10104 KB Output is correct
3 Correct 44 ms 10360 KB Output is correct
4 Correct 29 ms 10104 KB Output is correct
5 Correct 34 ms 9976 KB Output is correct
6 Correct 42 ms 10104 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8960 KB Output is correct
2 Correct 5 ms 8960 KB Output is correct
3 Correct 6 ms 8960 KB Output is correct
4 Correct 6 ms 8960 KB Output is correct
5 Correct 5 ms 8960 KB Output is correct
6 Correct 6 ms 8960 KB Output is correct
7 Correct 6 ms 8960 KB Output is correct
8 Correct 72 ms 53496 KB Output is correct
9 Correct 78 ms 51448 KB Output is correct
10 Correct 95 ms 17396 KB Output is correct
11 Correct 103 ms 17272 KB Output is correct
12 Correct 77 ms 37368 KB Output is correct
13 Correct 85 ms 37752 KB Output is correct
14 Correct 61 ms 18168 KB Output is correct
15 Correct 95 ms 33016 KB Output is correct
16 Correct 78 ms 30840 KB Output is correct
17 Correct 53 ms 26616 KB Output is correct
18 Correct 40 ms 10552 KB Output is correct
19 Correct 35 ms 10104 KB Output is correct
20 Correct 44 ms 10360 KB Output is correct
21 Correct 29 ms 10104 KB Output is correct
22 Correct 34 ms 9976 KB Output is correct
23 Correct 42 ms 10104 KB Output is correct
24 Correct 87 ms 46840 KB Output is correct
25 Correct 117 ms 47480 KB Output is correct
26 Correct 76 ms 46200 KB Output is correct
27 Correct 97 ms 17912 KB Output is correct
28 Correct 190 ms 22264 KB Output is correct
29 Correct 135 ms 14212 KB Output is correct