oj.uz

Submission #788691

# Submission time Handle Problem Language Result Execution time Memory
788691 2023-07-20T13:29:09 Z Dan4Life Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 284 ms 329328 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[mxN];
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 23 ms 50388 KB Output is correct
2 Correct 27 ms 50440 KB Output is correct
3 Correct 26 ms 50360 KB Output is correct
4 Correct 23 ms 50408 KB Output is correct
5 Correct 23 ms 50488 KB Output is correct
6 Correct 23 ms 50376 KB Output is correct
7 Correct 22 ms 50388 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 168952 KB Output is correct
2 Correct 263 ms 172940 KB Output is correct
3 Correct 147 ms 121060 KB Output is correct
4 Correct 151 ms 120900 KB Output is correct
5 Runtime error 284 ms 329328 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 101 ms 51692 KB Output is correct
2 Correct 74 ms 51656 KB Output is correct
3 Correct 90 ms 51700 KB Output is correct
4 Correct 77 ms 51504 KB Output is correct
5 Correct 80 ms 51700 KB Output is correct
6 Correct 91 ms 51604 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 50388 KB Output is correct
2 Correct 27 ms 50440 KB Output is correct
3 Correct 26 ms 50360 KB Output is correct
4 Correct 23 ms 50408 KB Output is correct
5 Correct 23 ms 50488 KB Output is correct
6 Correct 23 ms 50376 KB Output is correct
7 Correct 22 ms 50388 KB Output is correct
8 Correct 239 ms 168952 KB Output is correct
9 Correct 263 ms 172940 KB Output is correct
10 Correct 147 ms 121060 KB Output is correct
11 Correct 151 ms 120900 KB Output is correct
12 Runtime error 284 ms 329328 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -