oj.uz

Submission #715865

# Submission time Handle Problem Language Result Execution time Memory
715865 2023-03-28T08:47:36 Z rt144 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 148 ms 140108 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 140108 KB Output is correct
2 Correct 137 ms 133656 KB Output is correct
3 Correct 100 ms 107124 KB Output is correct
4 Correct 102 ms 102680 KB Output is correct
5 Correct 109 ms 134236 KB Output is correct
6 Correct 106 ms 136140 KB Output is correct
7 Correct 111 ms 28576 KB Output is correct
8 Correct 126 ms 101836 KB Output is correct
9 Correct 96 ms 90528 KB Output is correct
10 Correct 80 ms 83048 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3524 KB Output is correct
2 Correct 20 ms 3012 KB Output is correct
3 Correct 22 ms 3296 KB Output is correct
4 Correct 17 ms 2804 KB Output is correct
5 Correct 20 ms 3040 KB Output is correct
6 Correct 26 ms 3244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 126 ms 140108 KB Output is correct
9 Correct 137 ms 133656 KB Output is correct
10 Correct 100 ms 107124 KB Output is correct
11 Correct 102 ms 102680 KB Output is correct
12 Correct 109 ms 134236 KB Output is correct
13 Correct 106 ms 136140 KB Output is correct
14 Correct 111 ms 28576 KB Output is correct
15 Correct 126 ms 101836 KB Output is correct
16 Correct 96 ms 90528 KB Output is correct
17 Correct 80 ms 83048 KB Output is correct
18 Correct 23 ms 3524 KB Output is correct
19 Correct 20 ms 3012 KB Output is correct
20 Correct 22 ms 3296 KB Output is correct
21 Correct 17 ms 2804 KB Output is correct
22 Correct 20 ms 3040 KB Output is correct
23 Correct 26 ms 3244 KB Output is correct
24 Correct 133 ms 119244 KB Output is correct
25 Correct 148 ms 119408 KB Output is correct
26 Correct 132 ms 118044 KB Output is correct
27 Correct 116 ms 91736 KB Output is correct
28 Correct 141 ms 45716 KB Output is correct
29 Correct 77 ms 16532 KB Output is correct