Submission #896924

#	Time	Username	Problem	Language	Result	Execution time	Memory
896924		notyourbusiness	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	189 ms	187220 KiB

selling_rna

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
 
#define lb(x...) lower_bound(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
 
map<char, int> cmp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
 
struct T {
	array<T*, 4> nxt;
	vector<int> idx;
 
	
	template<class it>
	void insert(it st, it en, int i) {
		idx.push_back(i);
		if (st == en) return;
		auto &x = nxt[cmp[*st]];
		if (!x) x = new T();
		x->insert(next(st), en, i);
	}
 
	template<class it>
	int query(it st, it en, int l, int r) { // [l, r)
		if (st == en)
			return lb(all(idx), r) - lb(all(idx), l);
		auto &x = nxt[cmp[*st]];
		return x ? x->query(next(st), en, l, r) : 0;
	}
} t;
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m;
	cin >> n >> m;
	vector<string> s(n);
	rep(i, 0, n) cin >> s[i];
	sort(all(s));
	rep(i, 0, n) t.insert(rall(s[i]), i);
	while (m--) {
		string p, q; cin >> p >> q;
		int l = lb(all(s), p) - begin(s);
		++p.back();
		int r = lb(all(s), p) - begin(s);
		cout << t.query(rall(q), l, r) << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40