oj.uz

Submission #398813

# Submission time Handle Problem Language Result Execution time Memory
398813 2021-05-04T20:32:11 Z nikatamliani Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 403 ms 291656 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], tries;
vector<int> ids[40*N];
int nxt[40*N][4];
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);
}
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);
	for(int i = 1; i <= n; ++i) {
		int hash = 0;
		reverse(s[i].begin(), s[i].end());
		add(s[i], i);
		reverse(s[i].begin(), s[i].end());
	}
	for(int i = 1; i <= m; ++i) {
		string p, q; cin >> p >> q;
		int L = n+1, R = 0;
		L = find_first(p);
		if(!is_prefix(p, s[L])) {
			cout << "0\n";
			continue;
		}
		R = find_last(L, p); 
		if(L > R) {
			cout << "0\n";
			continue;
		}
		reverse(q.begin(), q.end());
		cout << get(q, L, R) << '\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 function 'void add(const string&, int)':
selling_rna.cpp:75:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |   if(nxt[cur][id[s[i]]] == 0) {
      |                      ^
selling_rna.cpp:76:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |    nxt[cur][id[s[i]]] = ++tries;
      |                    ^
selling_rna.cpp:78:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   78 |   cur = nxt[cur][id[s[i]]];
      |                         ^
selling_rna.cpp: In function 'int get(const string&, int, int)':
selling_rna.cpp:85:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |   cur = nxt[cur][id[s[i]]];
      |                         ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:101:7: warning: unused variable 'hash' [-Wunused-variable]
  101 |   int hash = 0;
      |       ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 194372 KB Output is correct
2 Correct 117 ms 194376 KB Output is correct
3 Correct 107 ms 194416 KB Output is correct
4 Correct 113 ms 194372 KB Output is correct
5 Correct 118 ms 194520 KB Output is correct
6 Correct 107 ms 194428 KB Output is correct
7 Correct 126 ms 194380 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 291656 KB Output is correct
2 Correct 328 ms 286392 KB Output is correct
3 Correct 188 ms 210608 KB Output is correct
4 Correct 186 ms 210224 KB Output is correct
5 Correct 251 ms 255424 KB Output is correct
6 Correct 240 ms 256204 KB Output is correct
7 Correct 198 ms 206184 KB Output is correct
8 Correct 296 ms 237440 KB Output is correct
9 Correct 266 ms 231808 KB Output is correct
10 Correct 253 ms 231300 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 195920 KB Output is correct
2 Correct 142 ms 195620 KB Output is correct
3 Correct 152 ms 195652 KB Output is correct
4 Correct 140 ms 195516 KB Output is correct
5 Correct 147 ms 195524 KB Output is correct
6 Correct 156 ms 195556 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 194372 KB Output is correct
2 Correct 117 ms 194376 KB Output is correct
3 Correct 107 ms 194416 KB Output is correct
4 Correct 113 ms 194372 KB Output is correct
5 Correct 118 ms 194520 KB Output is correct
6 Correct 107 ms 194428 KB Output is correct
7 Correct 126 ms 194380 KB Output is correct
8 Correct 297 ms 291656 KB Output is correct
9 Correct 328 ms 286392 KB Output is correct
10 Correct 188 ms 210608 KB Output is correct
11 Correct 186 ms 210224 KB Output is correct
12 Correct 251 ms 255424 KB Output is correct
13 Correct 240 ms 256204 KB Output is correct
14 Correct 198 ms 206184 KB Output is correct
15 Correct 296 ms 237440 KB Output is correct
16 Correct 266 ms 231808 KB Output is correct
17 Correct 253 ms 231300 KB Output is correct
18 Correct 152 ms 195920 KB Output is correct
19 Correct 142 ms 195620 KB Output is correct
20 Correct 152 ms 195652 KB Output is correct
21 Correct 140 ms 195516 KB Output is correct
22 Correct 147 ms 195524 KB Output is correct
23 Correct 156 ms 195556 KB Output is correct
24 Correct 328 ms 273164 KB Output is correct
25 Correct 367 ms 273228 KB Output is correct
26 Correct 313 ms 272264 KB Output is correct
27 Correct 201 ms 208196 KB Output is correct
28 Correct 403 ms 216656 KB Output is correct
29 Correct 262 ms 200964 KB Output is correct