oj.uz

Submission #398823

# Submission time Handle Problem Language Result Execution time Memory
398823 2021-05-04T20:44:58 Z nikatamliani Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 597 ms 712584 KB 
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5+10, p = 37, MOD = 1e9+7;
string s[N];
int n, m, P[N];
bool check(const string &a, const string &b) { // a >= b ? true : false
	int mini = min((int)a.size(), (int)b.size());
	for(int i = 0; i < mini; ++i) {
		if(a[i] != b[i]) {
			return a[i] > b[i];
		}
	}
	return mini == (int)b.size();
}
bool is_prefix(const string &a, const string &b) {
	if((int)a.size() > (int)b.size()) {
		return false;
	}
	for(int i = 0; i < (int)a.size(); ++i) {
		if(a[i] != b[i]) {
			return false;
		}
	}
	return true;
}
int find_first(const string &p) {
	int l = 1, r = n, pos = n+1;
	while(r >= l) {
		int m = l + r >> 1;
		if(check(s[m], p)) {
			r = m - 1;
			pos = m;
		} else {
			l = m + 1;
		}
	}
	return pos;
}
int find_last(int start, const string &p) {
	int l = start, r = n, pos = 0;
	while(r >= l) {
		int m = l + r >> 1;
		if(is_prefix(p, s[m])) {
			pos = m;
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	return pos;
}
int count(const vector<int> &v, int x) {
	if(v.empty()) return 0;
	int l = 0, r = (int)v.size()-1, pos = -1;
	while(r >= l) {
		int m = l + r >> 1;
		if(v[m] <= x) {
			pos = m;
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	return pos+1;
}
int count(const vector<int> &v, int L, int R) {
	return count(v, R) - count(v, L-1);
}
int id[256];
struct trie {
	int tries;
	vector<array<int, 4>> nxt;
	vector<vector<int>> ids;
	trie() {}
	trie(int size) {
		tries = 0;
		nxt = vector<array<int, 4>>(size);
		ids = vector<vector<int>>(size);
	}
	void add(const string &s, int pos) {
		int cur = 0;
		for(int i = 0; i < (int)s.size(); ++i) {
			if(nxt[cur][id[s[i]]] == 0) {
				nxt[cur][id[s[i]]] = ++tries;
			}
			cur = nxt[cur][id[s[i]]];
			ids[cur].push_back(pos);
	 	}
	}
	int get(const string &s, int L, int R) {
		int cur = 0;
		for(int i = 0; i < (int)s.size(); ++i) {
			cur = nxt[cur][id[s[i]]];
		}
		return count(ids[cur], L, R);
	}
	pair<int, int> get(const string &s) {
		int cur = 0;
		for(int i = 0; i < (int)s.size(); ++i) {
			cur = nxt[cur][id[s[i]]];
		}
		if(ids[cur].empty()) {
			return {0, 0};
		}
		return {ids[cur][0], ids[cur].back()};
	}
};
int main() {
	id['A'] = 1;
	id['U'] = 2;
	id['G'] = 3;
	id['C'] = 4;
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	sort(s+1, s+n+1);
	trie t1(40*N), t2(40*N);
	for(int i = 1; i <= n; ++i) {
		t1.add(s[i], i);
		reverse(s[i].begin(), s[i].end());
		t2.add(s[i], i);
		reverse(s[i].begin(), s[i].end());
	}
	for(int i = 1; i <= m; ++i) {
		string p, q; cin >> p >> q;
		reverse(q.begin(), q.end());
		pair<int, int> LR = t1.get(p);
		cout << t2.get(q, LR.first, LR.second) << '\n';
	}
}

Compilation message

selling_rna.cpp: In function 'int find_first(const string&)':
selling_rna.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int m = l + r >> 1;
      |           ~~^~~
selling_rna.cpp: In function 'int find_last(int, const string&)':
selling_rna.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int m = l + r >> 1;
      |           ~~^~~
selling_rna.cpp: In function 'int count(const std::vector<int>&, int)':
selling_rna.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int m = l + r >> 1;
      |           ~~^~~
selling_rna.cpp: In member function 'void trie::add(const string&, int)':
selling_rna.cpp:83:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |    if(nxt[cur][id[s[i]]] == 0) {
      |                       ^
selling_rna.cpp:84:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |     nxt[cur][id[s[i]]] = ++tries;
      |                     ^
selling_rna.cpp:86:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'int trie::get(const string&, int, int)':
selling_rna.cpp:93:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'std::pair<int, int> trie::get(const string&)':
selling_rna.cpp:100:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |    cur = nxt[cur][id[s[i]]];
      |                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 632848 KB Output is correct
2 Correct 352 ms 632780 KB Output is correct
3 Correct 352 ms 632772 KB Output is correct
4 Correct 349 ms 632892 KB Output is correct
5 Correct 354 ms 632832 KB Output is correct
6 Correct 347 ms 632948 KB Output is correct
7 Correct 367 ms 632884 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 708944 KB Output is correct
2 Correct 586 ms 705196 KB Output is correct
3 Correct 563 ms 708036 KB Output is correct
4 Correct 545 ms 704532 KB Output is correct
5 Correct 541 ms 711124 KB Output is correct
6 Correct 559 ms 712584 KB Output is correct
7 Correct 432 ms 652408 KB Output is correct
8 Correct 597 ms 692896 KB Output is correct
9 Correct 557 ms 684608 KB Output is correct
10 Correct 541 ms 683956 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 634640 KB Output is correct
2 Correct 385 ms 634392 KB Output is correct
3 Correct 376 ms 634432 KB Output is correct
4 Correct 370 ms 634608 KB Output is correct
5 Correct 377 ms 634384 KB Output is correct
6 Correct 379 ms 634412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 632848 KB Output is correct
2 Correct 352 ms 632780 KB Output is correct
3 Correct 352 ms 632772 KB Output is correct
4 Correct 349 ms 632892 KB Output is correct
5 Correct 354 ms 632832 KB Output is correct
6 Correct 347 ms 632948 KB Output is correct
7 Correct 367 ms 632884 KB Output is correct
8 Correct 583 ms 708944 KB Output is correct
9 Correct 586 ms 705196 KB Output is correct
10 Correct 563 ms 708036 KB Output is correct
11 Correct 545 ms 704532 KB Output is correct
12 Correct 541 ms 711124 KB Output is correct
13 Correct 559 ms 712584 KB Output is correct
14 Correct 432 ms 652408 KB Output is correct
15 Correct 597 ms 692896 KB Output is correct
16 Correct 557 ms 684608 KB Output is correct
17 Correct 541 ms 683956 KB Output is correct
18 Correct 382 ms 634640 KB Output is correct
19 Correct 385 ms 634392 KB Output is correct
20 Correct 376 ms 634432 KB Output is correct
21 Correct 370 ms 634608 KB Output is correct
22 Correct 377 ms 634384 KB Output is correct
23 Correct 379 ms 634412 KB Output is correct
24 Correct 576 ms 696840 KB Output is correct
25 Correct 584 ms 696984 KB Output is correct
26 Correct 579 ms 696256 KB Output is correct
27 Correct 561 ms 695840 KB Output is correct
28 Correct 556 ms 660004 KB Output is correct
29 Correct 443 ms 643688 KB Output is correct