제출 #86577

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

selling_rna

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int SIZEMAX = 2000005;
const int INF = 1000000005;

struct Node {
	int mn, mx, nxt[4]; vector<int> lis;
	Node() : mn(INF), mx(-INF) {
		memset(nxt, 0, sizeof nxt); } };

struct Event {
	int typ; pair<int, int> seg;
	Event(int _typ, pair<int, int> _seg) :
		typ(_typ), seg(_seg) {} };

string str[MAXN], rev[MAXN];
Node trie1[SIZEMAX], trie2[SIZEMAX];
vector<Event> evn[MAXN]; 
pair<int, int> sgx[MAXN], sgy[MAXN];

int bit[MAXN], ans[MAXN], psx[MAXN], psy[MAXN];

void insert(Node trie[], int &tot, int nd, int ps, string &str, int p) {
	if (ps != str.length()) {
		if (!trie[nd].nxt[str[ps]]) {
			trie[nd].nxt[str[ps]] = ++tot; }
		insert(trie, tot, trie[nd].nxt[str[ps]], ps + 1, str, p); } 
	else {
		trie[nd].lis.push_back(p); } }
		
void dfs(Node trie[], int &tot, int nd, int pos[]) {
	for (int x : trie[nd].lis) {
		pos[x] = ++tot; 
		trie[nd].mn = min(trie[nd].mn, tot); 
		trie[nd].mx = max(trie[nd].mx, tot); }
	for (int i = 0; i < 4; ++i) {
		if (trie[nd].nxt[i] != 0) {
			dfs(trie, tot, trie[nd].nxt[i], pos);
			trie[nd].mn = min(trie[nd].mn, trie[trie[nd].nxt[i]].mn);
			trie[nd].mx = max(trie[nd].mx, trie[trie[nd].nxt[i]].mx); } } }

int _mn, _mx;
void getMinMax(Node trie[], int nd, int ps, string &str) {
	if (ps == str.length()) {
		_mn = trie[nd].mn; _mx = trie[nd].mx; }
	else {
		if (!trie[nd].nxt[str[ps]]) {
			_mn = INF; _mx = -INF; }
		else {
			getMinMax(trie, trie[nd].nxt[str[ps]], ps + 1, str); } } } 

void changeString(string &str) {	
	for (char &ch : str) {
		if (ch == 'A') { ch = 0; }
		if (ch == 'C') { ch = 1; }
		if (ch == 'G') { ch = 2; }
		if (ch == 'U') { ch = 3; } } }

void update(int ps, int vl) {
	for (; ps < MAXN; ps += (ps & -ps)) {
		bit[ps] += vl; } }

int query(int ps, int vl = 0) {
	for (; ps > 0; ps -= (ps & -ps)) {
		vl += bit[ps]; }
	return vl; }

int main(void) {
#ifdef HOME
	freopen("sellrna.in", "r", stdin);
	freopen("sellrna.out", "w", stdout);
#endif
	int n, m; cin >> n >> m;
	for (int i = 1, nr1 = 1, nr2 = 1; i <= n; ++i) {
		cin >> str[i]; changeString(str[i]); 
		rev[i] = str[i]; reverse(rev[i].begin(), rev[i].end());
		insert(trie1, nr1, 1, 0, str[i], i); insert(trie2, nr2, 1, 0, rev[i], i); }
	int nr; nr = 0; dfs(trie1, nr, 1, psx); nr = 0; dfs(trie2, nr, 1, psy);
	for (int i = 1; i <= n; ++i) {
		evn[psx[i]].push_back(Event(0, make_pair(psy[i], psy[i]))); }
	for (int i = 1; i <= m; ++i) {
		string str1, str2; cin >> str1 >> str2; 
		changeString(str1); changeString(str2); reverse(str2.begin(), str2.end());
		getMinMax(trie1, 1, 0, str1); sgx[i] = make_pair(_mn, _mx);
		getMinMax(trie2, 1, 0, str2); sgy[i] = make_pair(_mn, _mx);
		if (sgx[i].first != INF and sgy[i].first != INF) {
			evn[sgx[i].first - 1].push_back(Event(-i, sgy[i]));
			evn[sgx[i].second].push_back(Event(i, sgy[i])); } }
	for (int i = 0; i <= n; ++i) {
		for (auto &ev : evn[i]) {
			if (ev.typ == 0) {
				update(ev.seg.first, 1); }
			else {
				ans[abs(ev.typ)] += (query(ev.seg.second) - query(ev.seg.first - 1)) * (ev.typ < 0 ? -1 : 1); } } }
	for (int i = 1; i <= m; ++i) {
		cout << ans[i] << "\n"; }
	return 0; }

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

selling_rna.cpp: In function 'void insert(Node*, int&, int, int, std::__cxx11::string&, int)':
selling_rna.cpp:26:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ps != str.length()) {
      ~~~^~~~~~~~~~~~~~~
selling_rna.cpp:27:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (!trie[nd].nxt[str[ps]]) {
                            ^
selling_rna.cpp:28:24: warning: array subscript has type 'char' [-Wchar-subscripts]
    trie[nd].nxt[str[ps]] = ++tot; }
                        ^
selling_rna.cpp:29:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   insert(trie, tot, trie[nd].nxt[str[ps]], ps + 1, str, p); } 
                                         ^
selling_rna.cpp: In function 'void getMinMax(Node*, int, int, std::__cxx11::string&)':
selling_rna.cpp:46:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ps == str.length()) {
      ~~~^~~~~~~~~~~~~~~
selling_rna.cpp:49:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (!trie[nd].nxt[str[ps]]) {
                            ^
selling_rna.cpp:52:40: warning: array subscript has type 'char' [-Wchar-subscripts]
    getMinMax(trie, trie[nd].nxt[str[ps]], ps + 1, str); } } } 
                                        ^

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