oj.uz

Submission #398812

# Submission time Handle Problem Language Result Execution time Memory
398812 2021-05-04T20:31:37 Z nikatamliani Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 406 ms 293520 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() {
	P[0] = 1;
	for(int i = 1; i < N; ++i) {
		P[i] = (long long)P[i - 1] * p % MOD;
	}
	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:105:7: warning: unused variable 'hash' [-Wunused-variable]
  105 |   int hash = 0;
      |       ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 195208 KB Output is correct
2 Correct 123 ms 195192 KB Output is correct
3 Correct 122 ms 195188 KB Output is correct
4 Correct 124 ms 195212 KB Output is correct
5 Correct 132 ms 195124 KB Output is correct
6 Correct 121 ms 195124 KB Output is correct
7 Correct 121 ms 195256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 293520 KB Output is correct
2 Correct 334 ms 288580 KB Output is correct
3 Correct 189 ms 212696 KB Output is correct
4 Correct 193 ms 212412 KB Output is correct
5 Correct 248 ms 256284 KB Output is correct
6 Correct 271 ms 257176 KB Output is correct
7 Correct 213 ms 210624 KB Output is correct
8 Correct 296 ms 242500 KB Output is correct
9 Correct 270 ms 236888 KB Output is correct
10 Correct 240 ms 233540 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 196600 KB Output is correct
2 Correct 150 ms 196568 KB Output is correct
3 Correct 160 ms 196340 KB Output is correct
4 Correct 152 ms 196292 KB Output is correct
5 Correct 156 ms 196268 KB Output is correct
6 Correct 162 ms 196488 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 195208 KB Output is correct
2 Correct 123 ms 195192 KB Output is correct
3 Correct 122 ms 195188 KB Output is correct
4 Correct 124 ms 195212 KB Output is correct
5 Correct 132 ms 195124 KB Output is correct
6 Correct 121 ms 195124 KB Output is correct
7 Correct 121 ms 195256 KB Output is correct
8 Correct 316 ms 293520 KB Output is correct
9 Correct 334 ms 288580 KB Output is correct
10 Correct 189 ms 212696 KB Output is correct
11 Correct 193 ms 212412 KB Output is correct
12 Correct 248 ms 256284 KB Output is correct
13 Correct 271 ms 257176 KB Output is correct
14 Correct 213 ms 210624 KB Output is correct
15 Correct 296 ms 242500 KB Output is correct
16 Correct 270 ms 236888 KB Output is correct
17 Correct 240 ms 233540 KB Output is correct
18 Correct 158 ms 196600 KB Output is correct
19 Correct 150 ms 196568 KB Output is correct
20 Correct 160 ms 196340 KB Output is correct
21 Correct 152 ms 196292 KB Output is correct
22 Correct 156 ms 196268 KB Output is correct
23 Correct 162 ms 196488 KB Output is correct
24 Correct 356 ms 276844 KB Output is correct
25 Correct 384 ms 277144 KB Output is correct
26 Correct 324 ms 275968 KB Output is correct
27 Correct 200 ms 211908 KB Output is correct
28 Correct 406 ms 220708 KB Output is correct
29 Correct 253 ms 203692 KB Output is correct