oj.uz

Submission #398829

# Submission time Handle Problem Language Result Execution time Memory
398829 2021-05-04T20:49:14 Z nikatamliani Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 324 ms 242028 KB 
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5+10;
string s[N];
int n, m;
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(10*N), t2(10*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 count(const std::vector<int>&, int)':
selling_rna.cpp:10:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |   int m = l + r >> 1;
      |           ~~^~~
selling_rna.cpp: In member function 'void trie::add(const string&, int)':
selling_rna.cpp:37:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |    if(nxt[cur][id[s[i]]] == 0) {
      |                       ^
selling_rna.cpp:38:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |     nxt[cur][id[s[i]]] = ++tries;
      |                     ^
selling_rna.cpp:40:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'int trie::get(const string&, int, int)':
selling_rna.cpp:47:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'std::pair<int, int> trie::get(const string&)':
selling_rna.cpp:54:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |    cur = nxt[cur][id[s[i]]];
      |                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 163140 KB Output is correct
2 Correct 85 ms 163148 KB Output is correct
3 Correct 85 ms 163084 KB Output is correct
4 Correct 84 ms 163036 KB Output is correct
5 Correct 85 ms 163032 KB Output is correct
6 Correct 85 ms 163092 KB Output is correct
7 Correct 84 ms 163064 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 238276 KB Output is correct
2 Correct 300 ms 234428 KB Output is correct
3 Correct 274 ms 236920 KB Output is correct
4 Correct 270 ms 233452 KB Output is correct
5 Correct 279 ms 240856 KB Output is correct
6 Correct 277 ms 242028 KB Output is correct
7 Correct 165 ms 181572 KB Output is correct
8 Correct 324 ms 222100 KB Output is correct
9 Correct 280 ms 213700 KB Output is correct
10 Correct 266 ms 212888 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 164536 KB Output is correct
2 Correct 108 ms 164368 KB Output is correct
3 Correct 112 ms 164408 KB Output is correct
4 Correct 106 ms 164428 KB Output is correct
5 Correct 108 ms 164284 KB Output is correct
6 Correct 113 ms 164340 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 163140 KB Output is correct
2 Correct 85 ms 163148 KB Output is correct
3 Correct 85 ms 163084 KB Output is correct
4 Correct 84 ms 163036 KB Output is correct
5 Correct 85 ms 163032 KB Output is correct
6 Correct 85 ms 163092 KB Output is correct
7 Correct 84 ms 163064 KB Output is correct
8 Correct 299 ms 238276 KB Output is correct
9 Correct 300 ms 234428 KB Output is correct
10 Correct 274 ms 236920 KB Output is correct
11 Correct 270 ms 233452 KB Output is correct
12 Correct 279 ms 240856 KB Output is correct
13 Correct 277 ms 242028 KB Output is correct
14 Correct 165 ms 181572 KB Output is correct
15 Correct 324 ms 222100 KB Output is correct
16 Correct 280 ms 213700 KB Output is correct
17 Correct 266 ms 212888 KB Output is correct
18 Correct 112 ms 164536 KB Output is correct
19 Correct 108 ms 164368 KB Output is correct
20 Correct 112 ms 164408 KB Output is correct
21 Correct 106 ms 164428 KB Output is correct
22 Correct 108 ms 164284 KB Output is correct
23 Correct 113 ms 164340 KB Output is correct
24 Correct 303 ms 225744 KB Output is correct
25 Correct 310 ms 225996 KB Output is correct
26 Correct 300 ms 225256 KB Output is correct
27 Correct 275 ms 224964 KB Output is correct
28 Correct 290 ms 189372 KB Output is correct
29 Correct 184 ms 172980 KB Output is correct