Submission #216486

#	Time	Username	Problem	Language	Result	Execution time	Memory
216486		islingr	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	280 ms	191156 KiB

selling_rna

#include <array>
#include <typeinfo>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)

#define sz(x) int((x).size())
#define lb(x...) lower_bound(x)
#define ub(x...) upper_bound(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define eb(x...) emplace_back(x)

constexpr int A = 4;

map<char, int> cmp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};

struct T {
	array<T*, A> nxt;
	vector<int> idx;

	T() { fill(all(nxt), nullptr); }

	template<class it>
	void insert(it st, it en, int i) {
		idx.eb(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 = ub(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