oj.uz

Submission #398827

# Submission time Handle Problem Language Result Execution time Memory
398827 2021-05-04T20:47:08 Z nikatamliani Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 402 ms 398676 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(20*N), t2(20*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 163 ms 319684 KB Output is correct
2 Correct 162 ms 319796 KB Output is correct
3 Correct 162 ms 319656 KB Output is correct
4 Correct 176 ms 319632 KB Output is correct
5 Correct 167 ms 319684 KB Output is correct
6 Correct 164 ms 319840 KB Output is correct
7 Correct 161 ms 319660 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 394956 KB Output is correct
2 Correct 373 ms 390856 KB Output is correct
3 Correct 353 ms 393572 KB Output is correct
4 Correct 355 ms 390220 KB Output is correct
5 Correct 350 ms 397432 KB Output is correct
6 Correct 358 ms 398676 KB Output is correct
7 Correct 237 ms 338176 KB Output is correct
8 Correct 402 ms 378652 KB Output is correct
9 Correct 352 ms 370284 KB Output is correct
10 Correct 334 ms 369496 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 321088 KB Output is correct
2 Correct 186 ms 320940 KB Output is correct
3 Correct 190 ms 320964 KB Output is correct
4 Correct 181 ms 320932 KB Output is correct
5 Correct 185 ms 320960 KB Output is correct
6 Correct 193 ms 320904 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 319684 KB Output is correct
2 Correct 162 ms 319796 KB Output is correct
3 Correct 162 ms 319656 KB Output is correct
4 Correct 176 ms 319632 KB Output is correct
5 Correct 167 ms 319684 KB Output is correct
6 Correct 164 ms 319840 KB Output is correct
7 Correct 161 ms 319660 KB Output is correct
8 Correct 372 ms 394956 KB Output is correct
9 Correct 373 ms 390856 KB Output is correct
10 Correct 353 ms 393572 KB Output is correct
11 Correct 355 ms 390220 KB Output is correct
12 Correct 350 ms 397432 KB Output is correct
13 Correct 358 ms 398676 KB Output is correct
14 Correct 237 ms 338176 KB Output is correct
15 Correct 402 ms 378652 KB Output is correct
16 Correct 352 ms 370284 KB Output is correct
17 Correct 334 ms 369496 KB Output is correct
18 Correct 187 ms 321088 KB Output is correct
19 Correct 186 ms 320940 KB Output is correct
20 Correct 190 ms 320964 KB Output is correct
21 Correct 181 ms 320932 KB Output is correct
22 Correct 185 ms 320960 KB Output is correct
23 Correct 193 ms 320904 KB Output is correct
24 Correct 392 ms 382296 KB Output is correct
25 Correct 394 ms 382624 KB Output is correct
26 Correct 383 ms 381764 KB Output is correct
27 Correct 354 ms 381700 KB Output is correct
28 Correct 368 ms 346016 KB Output is correct
29 Correct 261 ms 329604 KB Output is correct