oj.uz

Submission #788692

# Submission time Handle Problem Language Result Execution time Memory
788692 2023-07-20T13:31:39 Z Dan4Life Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 349 ms 448556 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;
int trie[2][4][mxS];
int L[mxS], R[mxS];
int n,m,node=2;
string s[mxS];
vector<int> xd[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++;
		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);
		if(!trie[t][c][v]) return 0;
		v = trie[t][c][v];
	}
	return v;
}

int32_t main()
{
	cin >> n >> m;
	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])-1;
		cout << max(0, pos2-pos1+1) << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 109900 KB Output is correct
2 Correct 45 ms 109900 KB Output is correct
3 Correct 52 ms 109908 KB Output is correct
4 Correct 53 ms 109856 KB Output is correct
5 Correct 45 ms 109872 KB Output is correct
6 Correct 61 ms 109996 KB Output is correct
7 Correct 47 ms 109900 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 224580 KB Output is correct
2 Correct 280 ms 228692 KB Output is correct
3 Correct 168 ms 176588 KB Output is correct
4 Correct 170 ms 176508 KB Output is correct
5 Runtime error 349 ms 448556 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 110664 KB Output is correct
2 Correct 100 ms 110820 KB Output is correct
3 Correct 132 ms 110832 KB Output is correct
4 Correct 105 ms 110628 KB Output is correct
5 Correct 101 ms 110752 KB Output is correct
6 Correct 114 ms 110736 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 109900 KB Output is correct
2 Correct 45 ms 109900 KB Output is correct
3 Correct 52 ms 109908 KB Output is correct
4 Correct 53 ms 109856 KB Output is correct
5 Correct 45 ms 109872 KB Output is correct
6 Correct 61 ms 109996 KB Output is correct
7 Correct 47 ms 109900 KB Output is correct
8 Correct 276 ms 224580 KB Output is correct
9 Correct 280 ms 228692 KB Output is correct
10 Correct 168 ms 176588 KB Output is correct
11 Correct 170 ms 176508 KB Output is correct
12 Runtime error 349 ms 448556 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -