제출 #398812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398812		nikatamliani	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	406 ms	293520 KiB

selling_rna

#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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40