Submission #1163893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163893		canhnam357	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	582 ms	281756 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MASK(i) (1LL << (i))
const int mod1 = 1035972859;
const int mod2 = 1704760909;
const int base = 256;
struct hashing
{
	int mod;
	vector<int> h, p, inv;
	hashing() {}
	hashing(int mod, string s)
	{
		int n = s.length();
		this->mod = mod;
		h.resize(n);
		p.resize(n);
		inv.resize(n);
		h[0] = s[0];
		p[0] = 1;
		for (int i = 1; i < n; i++)
		{
			p[i] = (p[i - 1] * base) % mod;
			h[i] = (h[i - 1] + s[i] * p[i]) % mod;
		}
		inv[n - 1] = power(p[n - 1], mod - 2);
		for (int i = n - 2; i >= 0; i--) inv[i] = (inv[i + 1] * base) % mod;
		reverse(s.begin(), s.end());
	}
	int power(int a, int b)
	{
		int ans = 1;
		while (b)
		{
			if (b & 1) ans = (ans * a) % mod;
			(a *= a) %= mod;
			b >>= 1;
		}
		return ans;
	}
	int get(int l, int r)
	{
		if (l > r) return 0;
		return l ? ((h[r] - h[l - 1] + mod) * inv[l]) % mod : h[r];
	}
	bool same(int l1, int r1, int l2, int r2)
	{
		return get(l1, r1) == get(l2, r2);
	}
};
int pos[256];
struct Trie
{
	Trie* child[4];
	vector<int> pos;
	Trie()
	{
		for (int i = 0; i < 4; i++) child[i] = NULL;
	}
};
Trie* p = new Trie();
void update(string s, int k)
{
	auto t = p;
	for (char c : s)
	{
		if (t->child[pos[c]] == NULL) t->child[pos[c]] = new Trie();
		t = t->child[pos[c]];
		t->pos.push_back(k);
	}
}
int get(string s, int l, int r)
{
	if (l > r) return 0;
	auto t = p;
	for (char c : s)
	{
		if (t->child[pos[c]] == NULL) return 0;
		t = t->child[pos[c]];
	}
	return upper_bound(t->pos.begin(), t->pos.end(), r) - lower_bound(t->pos.begin(), t->pos.end(), l);
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	pos['A'] = 0;
	pos['C'] = 1;
	pos['G'] = 2;
	pos['U'] = 3;
	int n, nq;
	cin >> n >> nq;
	vector<string> v(n);
	for (string& s : v) cin >> s;
	vector<hashing> h1, h2;
	for (string s : v) h1.push_back(hashing(mod1, s)), h2.push_back(hashing(mod2, s));
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int i, int j) {
		if (h1[i].h.back() == h1[j].h.back() && h2[i].h.back() == h2[j].h.back()) return false;
		if (v[i].length() < v[j].length())
		{
			if (h1[i].h.back() == h1[j].get(0, v[i].length() - 1) && h2[i].h.back() == h2[j].get(0, v[i].length() - 1)) return true;
			int l = -1, r = v[i].length();
			while (r - l > 1)
			{
				int m = (l + r) >> 1;
				if (h1[i].h[m] == h1[j].h[m] && h2[i].h[m] == h2[j].h[m]) l = m;
				else r = m;
			}
			return v[i][l + 1] < v[j][l + 1];
		}
		else
		{
			if (h1[j].h.back() == h1[i].get(0, v[j].length() - 1) && h2[j].h.back() == h2[i].get(0, v[j].length() - 1)) return false;
			int l = -1, r = v[j].length();
			while (r - l > 1)
			{
				int m = (l + r) >> 1;
				if (h1[i].h[m] == h1[j].h[m] && h2[i].h[m] == h2[j].h[m]) l = m;
				else r = m;
			}
			return v[i][l + 1] < v[j][l + 1];
		}
	});
	for (int i = 0; i < n; i++)
	{
		string s = v[ord[i]];
		reverse(s.begin(), s.end());
		update(s, i);
	}
	for (int _ = 0; _ < nq; _++)
	{
		string s, suf;
		cin >> s >> suf;
		hashing hs1(mod1, s), hs2(mod2, s);
		int low, high;
		{
			int l = -1, r = n;
			while (r - l > 1)
			{
				int m = (l + r) >> 1;
				int left = -1, right = min(s.length(), v[ord[m]].length());
				while (right - left > 1)
				{
					int mid = (left + right) >> 1;
					if (h1[ord[m]].h[mid] == hs1.h[mid] && h2[ord[m]].h[mid] == hs2.h[mid]) left = mid;
					else right = mid;
				}
				if (left + 1 == min(s.length(), v[ord[m]].length()))
				{
					if (s.length() <= v[ord[m]].length()) r = m;
					else l = m;
				}
				else
				{
					if (s[left + 1] > v[ord[m]][left + 1]) l = m;
					else r = m;
				}
			}
			low = r;
		}
		{
			int l = -1, r = n;
			while (r - l > 1)
			{
				int m = (l + r) >> 1;
				int left = -1, right = min(s.length(), v[ord[m]].length());
				while (right - left > 1)
				{
					int mid = (left + right) >> 1;
					if (h1[ord[m]].h[mid] == hs1.h[mid] && h2[ord[m]].h[mid] == hs2.h[mid]) left = mid;
					else right = mid;
				}
				if (left + 1 == min(s.length(), v[ord[m]].length()))
				{
					l = m;
				}
				else
				{
					if (s[left + 1] > v[ord[m]][left + 1]) l = m;
					else r = m;
				}
			}
			high = l;
		}
		/*cout << low << ' ' << high << '\n';
		for (int i = low; i <= high; i++) cout << v[ord[i]] << ' ';
		cout << '\n';*/
		reverse(suf.begin(), suf.end());
		cout << get(suf, low, high) << '\n';
	}
	return 0;
}

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