Submission #213418

#	Time	Username	Problem	Language	Result	Execution time	Memory
213418		tselmegkh	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	380 ms	214516 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40