제출 #398823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398823		nikatamliani	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	597 ms	712584 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];
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(40*N), t2(40*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';
	}
}

컴파일 시 표준 에러 (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 member function 'void trie::add(const string&, int)':
selling_rna.cpp:83:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |    if(nxt[cur][id[s[i]]] == 0) {
      |                       ^
selling_rna.cpp:84:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |     nxt[cur][id[s[i]]] = ++tries;
      |                     ^
selling_rna.cpp:86:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'int trie::get(const string&, int, int)':
selling_rna.cpp:93:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'std::pair<int, int> trie::get(const string&)':
selling_rna.cpp:100:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |    cur = nxt[cur][id[s[i]]];
      |                          ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40