Submission #848308

#	Time	Username	Problem	Language	Result	Execution time	Memory
848308		qthang2k11	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1272 ms	193244 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define next defined_next

const int mod = 1e9 + 696969, base = 311;

const int N = 1e5 + 5, S = sqrt(N);
vector<int> hs[N];
string s[N];
int n, q;

struct Node {
	int cnt;
	Node *nxt[4];
	
	Node() {
		cnt = 0;
		for (int i = 0; i < 4; i++)
			nxt[i] = nullptr;
	}
	
	Node *next(int x) {
		if (nxt[x] == nullptr)
			nxt[x] = new Node();
		return nxt[x];
	}
};

struct Trie {
	Node *root = new Node();
	
	Trie() = default;
	
	void insert(string s) {
		reverse(s.begin(), s.end());
		Node *cur = root;
		for (char ch: s) {
			cur = cur->next(ch);
			cur->cnt++;
		}
	}
	
	int get(string s) {
		reverse(s.begin(), s.end());
		Node *cur = root;
		for (char ch: s) {
			if (cur->nxt[(int)ch] == nullptr)
				return 0;
			cur = cur->nxt[(int)ch];
		}
		return cur->cnt;
	}
} blocks[N / S + 5];

map<char, int> mp;
void compress(string &s) {
	for (char &ch: s)
		ch = mp[ch];
}

void print_debug(string s, bool el = true) {
	map<char, char> rev;
	rev[0] = 'A';
	rev[1] = 'C';
	rev[2] = 'G';
	rev[3] = 'U';
	for (char c: s)
		cerr << rev[c];
	if (el) cerr << '\n';
}

struct pr {
	string s;
	vector<int> hs;
	
	pr() = default;
	pr(const string &str) {
		s = str;
		int n = s.size();
		hs.resize(n + 1);
		hs[0] = 1;
		for (int i = 1; i <= n; i++)
			hs[i] = (1LL * hs[i - 1] * base % mod + s[i - 1] + 1) % mod;
	}
	
	bool operator < (const pr &other) const {
		int len_x = s.size(), len_y = other.s.size();
		int l = 1, r = min(len_x, len_y), last_equal = 0;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (hs[mid] == other.hs[mid]) {
				last_equal = mid;
				l = mid + 1;
			} else r = mid - 1;
		}
		if (last_equal == len_x && last_equal == len_y)
			return false;
		if (last_equal == len_x || s[last_equal] < other.s[last_equal])
			return true;
		return false;
	}
	
} to_sort[N];

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("rna.inp", "r"))
		freopen("rna.inp", "r", stdin),
		freopen("rna.out", "w", stdout);
	mp['A'] = 0;
	mp['C'] = 1;
	mp['G'] = 2;
	mp['U'] = 3;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		compress(s[i]);
		to_sort[i] = pr(s[i]);
	}
	sort(to_sort, to_sort + n);
	for (int i = 0; i < n; i++)
		s[i] = to_sort[i].s;
	// cerr << "SORTED:\n";
	// for (int i = 0; i < n; i++)
		// print_debug(s[i]);
	for (int i = 0; i < n; i++) 
		blocks[i / S].insert(s[i]);
	while (q--) {
		string pre, suf;
		cin >> pre >> suf;
		compress(pre);
		compress(suf);
		int pre_len = pre.size(), suf_len = suf.size();
		int l = [&] () -> int {
			int l = 0, r = n - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (s[mid] >= pre) {
					ans = mid;
					r = mid - 1;
				} else l = mid + 1;
			}
			if (ans != -1 && (int)s[ans].size() >= pre_len && s[ans].substr(0, pre_len) == pre)
				return ans;
			return -1;
		}();
		int r = [&] (int l) -> int {
			int r = n - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if ((int)s[mid].size() >= pre_len && s[mid].substr(0, pre_len) == pre) {
					ans = mid;
					l = mid + 1;
				} else r = mid - 1;
			}
			if (ans != -1 && (int)s[ans].size() >= pre_len && s[ans].substr(0, pre_len) == pre)
				return ans;
			return -1;
		}(l);
		if (l != -1 && r != -1 && l <= r) {
			cout << ([&] () -> int {
				int res = 0;
				Trie ans;
				int blockl = l / S, blockr = r / S;
				if (blockl == blockr) {
					for (int i = l; i <= r; i++) 
						if ((int)s[i].size() >= suf_len)
							ans.insert(s[i].substr((int)s[i].size() - suf_len));
					res = ans.get(suf);
				} else {
					for (int i = (blockl + 1) * S - 1; i >= l; i--)
						if ((int)s[i].size() >= suf_len)
							ans.insert(s[i].substr((int)s[i].size() - suf_len));
					for (int i = blockr * S; i <= r; i++)
						if ((int)s[i].size() >= suf_len)
							ans.insert(s[i].substr((int)s[i].size() - suf_len));
					res = ans.get(suf);
					for (int i = blockl + 1; i < blockr; i++)
						res += blocks[i].get(suf);
				}
				return res;
			}());
		} else cout << 0;
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:111:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen("rna.inp", "r", stdin),
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen("rna.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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