oj.uz

Submission #788698

# Submission time Handle Problem Language Result Execution time Memory
788698 2023-07-20T13:38:42 Z Dan4Life Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 343 ms 205308 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)
const int mxN = (int)1e5+10;
const int mxS = (int)2e6+10;
vector<int> xd[mxS];
int trie[2][4][mxS];
int L[mxS], R[mxS];
int n, m, node[2];
string s[mxS];

void add(string &s, int ind, int t){
	int v = 1;
	for(auto u : s){
		int c = (u=='A'?0:u=='C'?1:u=='G'?2:3);
		if(!trie[t][c][v]) trie[t][c][v]=node[t]++;
		v = trie[t][c][v];
		if(!t){
			if(!L[v]) L[v]=ind;
			R[v]=max(R[v],ind);
		}
		else xd[v].pb(ind);
	}
}

int get(string &s, int t){
	int v = 1;
	for(auto u : s){
		int c = (u=='A'?0:u=='C'?1:u=='G'?2:3);
		v = trie[t][c][v]; if(!v) return 0;
	}
	return v;
}

int32_t main()
{
	cin >> n >> m; node[0]=node[1]=2;
	for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
	for(int i = 0; i < n; i++)
		add(s[i],i+1,0),reverse(all(s[i])),add(s[i],i+1,1);
	for(int i = 0; i < m; i++){
		string s, t; cin >> s >> t; reverse(all(t));
		int ind = get(s,0), ind2=get(t,1);
		int l = L[ind], r=R[ind];
		if(!l or !ind or !ind2) { cout << "0\n"; continue; }
		int pos1 = lower_bound(all(xd[ind2]),l)-begin(xd[ind2]);
		int pos2 = upper_bound(all(xd[ind2]),r)-begin(xd[ind2]);
		cout << max(0, pos2-pos1) << "\n";
	}
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:39:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   39 |  for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
      |  ^~~
selling_rna.cpp:39:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
      |                                          ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 109900 KB Output is correct
2 Correct 48 ms 109964 KB Output is correct
3 Correct 48 ms 109844 KB Output is correct
4 Correct 49 ms 109912 KB Output is correct
5 Correct 52 ms 109960 KB Output is correct
6 Correct 47 ms 109888 KB Output is correct
7 Correct 47 ms 109964 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 205308 KB Output is correct
2 Correct 221 ms 200400 KB Output is correct
3 Correct 163 ms 169712 KB Output is correct
4 Correct 163 ms 167324 KB Output is correct
5 Correct 191 ms 198760 KB Output is correct
6 Correct 202 ms 201252 KB Output is correct
7 Correct 158 ms 125828 KB Output is correct
8 Correct 228 ms 161712 KB Output is correct
9 Correct 220 ms 162196 KB Output is correct
10 Correct 173 ms 158540 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 111032 KB Output is correct
2 Correct 103 ms 110780 KB Output is correct
3 Correct 120 ms 110760 KB Output is correct
4 Correct 105 ms 110536 KB Output is correct
5 Correct 102 ms 110792 KB Output is correct
6 Correct 126 ms 110752 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 109900 KB Output is correct
2 Correct 48 ms 109964 KB Output is correct
3 Correct 48 ms 109844 KB Output is correct
4 Correct 49 ms 109912 KB Output is correct
5 Correct 52 ms 109960 KB Output is correct
6 Correct 47 ms 109888 KB Output is correct
7 Correct 47 ms 109964 KB Output is correct
8 Correct 222 ms 205308 KB Output is correct
9 Correct 221 ms 200400 KB Output is correct
10 Correct 163 ms 169712 KB Output is correct
11 Correct 163 ms 167324 KB Output is correct
12 Correct 191 ms 198760 KB Output is correct
13 Correct 202 ms 201252 KB Output is correct
14 Correct 158 ms 125828 KB Output is correct
15 Correct 228 ms 161712 KB Output is correct
16 Correct 220 ms 162196 KB Output is correct
17 Correct 173 ms 158540 KB Output is correct
18 Correct 135 ms 111032 KB Output is correct
19 Correct 103 ms 110780 KB Output is correct
20 Correct 120 ms 110760 KB Output is correct
21 Correct 105 ms 110536 KB Output is correct
22 Correct 102 ms 110792 KB Output is correct
23 Correct 126 ms 110752 KB Output is correct
24 Correct 244 ms 192612 KB Output is correct
25 Correct 296 ms 192812 KB Output is correct
26 Correct 231 ms 191640 KB Output is correct
27 Correct 224 ms 164596 KB Output is correct
28 Correct 343 ms 136336 KB Output is correct
29 Correct 255 ms 118432 KB Output is correct