Submission #715865

#	Time	Username	Problem	Language	Result	Execution time	Memory
715865		rt144	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	148 ms	140108 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
int n, m; struct pi { int l, r; };

int ctoi(char a) {
	if (a=='A') return 0;
	if (a=='G') return 1;
	if (a=='C') return 2;
	return 3;
}
static char buf[450 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i); return (void*)&buf[i -= s];
}
void operator delete(void*) noexcept {}
struct PTrie {
	int l = 0, r = 1e5+1;
	PTrie* ch[4]={nullptr, nullptr, nullptr, nullptr};
	void insert(string &a, int si, int i) {
		if (si==a.size()) { return; }
		int nx = ctoi(a[si]);
		if (!ch[nx]) ch[nx] = new PTrie{}, ch[nx]->r = ch[nx]->l = i;
		else ch[nx]->r = i; // i will always be the latest we have seen
 		ch[nx]->insert(a, si+1, i);
	}
	pi prefix(string &a, int si) {
		if (si==a.size()) return {l, r};
		int nx = ctoi(a[si]);
		if (ch[nx]) return ch[nx]->prefix(a, si+1);
		else return {-1, -1};
	}
};

struct QTrie {
	vector<int> ss; bool std = false;
	QTrie* ch[4]={nullptr, nullptr, nullptr, nullptr};
	void insert(string &a, int si, int i) {
		if (si==a.size()) { return; }
		int nx = ctoi(a[si]);
		if (!ch[nx]) ch[nx] = new QTrie{};
		ch[nx]->ss.push_back(i);
 		ch[nx]->insert(a, si+1, i);
	}
	int prefix(string &a, int si, int l, int r) {
		if (si==a.size()) {
			if (!std) sort(begin(ss), end(ss)), std = true;
			return upper_bound(begin(ss), end(ss), r)-lower_bound(begin(ss), end(ss), l);
		}
		int nx = ctoi(a[si]);
		if (ch[nx]) return ch[nx]->prefix(a, si+1, l, r);
		else return 0;
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m; vector<string> S(n);
	PTrie pt; QTrie qt;
	for (int i=0;i<n;i++) cin >> S[i];
	sort(begin(S), end(S));
	for (int i=0;i<n;i++) pt.insert(S[i], 0, i), reverse(begin(S[i]), end(S[i])), qt.insert(S[i], 0, i);
	for (int i=0;i<m;i++) {
		string p, q; cin >> p >> q; reverse(begin(q), end(q));
		auto [l, r] = pt.prefix(p, 0);
		cout << qt.prefix(q, 0, l, r) << '\n';
	}
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void PTrie::insert(std::string&, int, int)':
selling_rna.cpp:21:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if (si==a.size()) { return; }
      |       ~~^~~~~~~~~~
selling_rna.cpp: In member function 'pi PTrie::prefix(std::string&, int)':
selling_rna.cpp:28:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if (si==a.size()) return {l, r};
      |       ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void QTrie::insert(std::string&, int, int)':
selling_rna.cpp:39:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if (si==a.size()) { return; }
      |       ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int QTrie::prefix(std::string&, int, int, int)':
selling_rna.cpp:46:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (si==a.size()) {
      |       ~~^~~~~~~~~~

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