oj.uz

Submission #213418

# Submission time Handle Problem Language Result Execution time Memory
213418 2020-03-25T18:20:59 Z tselmegkh Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 380 ms 214516 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e6 + 5, inf = 1e9;
#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

map<char, int> ma;
struct trie{
	vi at[N];
	int to[N][4];
	int d = 1;

	void add(string x, int idx){
		int v = 0;
		for(int i = 0; i < sz(x); i++){
			if(!to[v][ma[x[i]]]){
				to[v][ma[x[i]]] = d++;
			}
			v = to[v][ma[x[i]]];
			at[v].pb(idx);
		}
	}
	ii q1(string x){
		int v = 0;
		for(int i = 0; i < sz(x); i++){
			if(!to[v][ma[x[i]]])return {-1, -1};
			v = to[v][ma[x[i]]];
		}
		return {at[v][0], at[v].back()};
	}
	int q2(int l, int r, string x){
		int v = 0;
		for(int i = 0; i < sz(x); i++){
			if(!to[v][ma[x[i]]])return 0;
			v = to[v][ma[x[i]]];
		}
		return upper_bound(all(at[v]), r) - lower_bound(all(at[v]), l);
	}
}a, b;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n, m;
	cin >> n >> m;
	ma['A'] = 0;
	ma['C'] = 1;
	ma['G'] = 2;
	ma['U'] = 3;
	vector<string> v;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		v.pb(s);
	}
	sort(all(v));
	for(int i = 0; i < n; i++){
		a.add(v[i], i);
		reverse(all(v[i]));
		b.add(v[i], i);
	}	
	for(int i = 0; i < m; i++){
		string p, q;
		cin >> p >> q;
		reverse(all(q));
		ii res1 = a.q1(p);
		if(res1 == mp(-1, -1)){
			cout << "0\n";
			continue;
		}
		cout << b.q2(res1.ff, res1.ss, q) << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Output is correct
2 Correct 61 ms 94332 KB Output is correct
3 Correct 55 ms 94328 KB Output is correct
4 Correct 53 ms 94328 KB Output is correct
5 Correct 54 ms 94328 KB Output is correct
6 Correct 53 ms 94328 KB Output is correct
7 Correct 53 ms 94328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 204152 KB Output is correct
2 Correct 366 ms 198772 KB Output is correct
3 Correct 372 ms 202616 KB Output is correct
4 Correct 365 ms 197876 KB Output is correct
5 Correct 350 ms 212852 KB Output is correct
6 Correct 336 ms 214516 KB Output is correct
7 Correct 171 ms 118264 KB Output is correct
8 Correct 349 ms 181492 KB Output is correct
9 Correct 310 ms 169460 KB Output is correct
10 Correct 278 ms 165876 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 98028 KB Output is correct
2 Correct 82 ms 97012 KB Output is correct
3 Correct 87 ms 97260 KB Output is correct
4 Correct 80 ms 97004 KB Output is correct
5 Correct 85 ms 97008 KB Output is correct
6 Correct 89 ms 97256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Output is correct
2 Correct 61 ms 94332 KB Output is correct
3 Correct 55 ms 94328 KB Output is correct
4 Correct 53 ms 94328 KB Output is correct
5 Correct 54 ms 94328 KB Output is correct
6 Correct 53 ms 94328 KB Output is correct
7 Correct 53 ms 94328 KB Output is correct
8 Correct 369 ms 204152 KB Output is correct
9 Correct 366 ms 198772 KB Output is correct
10 Correct 372 ms 202616 KB Output is correct
11 Correct 365 ms 197876 KB Output is correct
12 Correct 350 ms 212852 KB Output is correct
13 Correct 336 ms 214516 KB Output is correct
14 Correct 171 ms 118264 KB Output is correct
15 Correct 349 ms 181492 KB Output is correct
16 Correct 310 ms 169460 KB Output is correct
17 Correct 278 ms 165876 KB Output is correct
18 Correct 95 ms 98028 KB Output is correct
19 Correct 82 ms 97012 KB Output is correct
20 Correct 87 ms 97260 KB Output is correct
21 Correct 80 ms 97004 KB Output is correct
22 Correct 85 ms 97008 KB Output is correct
23 Correct 89 ms 97256 KB Output is correct
24 Correct 371 ms 186476 KB Output is correct
25 Correct 380 ms 186736 KB Output is correct
26 Correct 372 ms 185452 KB Output is correct
27 Correct 369 ms 185328 KB Output is correct
28 Correct 346 ms 131804 KB Output is correct
29 Correct 190 ms 110816 KB Output is correct