답안 #86577 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86577	2018-11-26T17:01:54 Z	KCSC	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	583 ms	274244 KB

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

Compilation message

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	185 ms	197112 KB	Output is correct
2	Correct	188 ms	197112 KB	Output is correct
3	Correct	186 ms	197112 KB	Output is correct
4	Correct	186 ms	197112 KB	Output is correct
5	Correct	186 ms	197112 KB	Output is correct
6	Correct	197 ms	197112 KB	Output is correct
7	Correct	192 ms	197112 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	439 ms	202484 KB	Output is correct
2	Correct	437 ms	206872 KB	Output is correct
3	Correct	450 ms	210740 KB	Output is correct
4	Correct	455 ms	214676 KB	Output is correct
5	Correct	447 ms	215392 KB	Output is correct
6	Correct	506 ms	217812 KB	Output is correct
7	Correct	417 ms	223520 KB	Output is correct
8	Correct	532 ms	230584 KB	Output is correct
9	Correct	536 ms	236320 KB	Output is correct
10	Correct	454 ms	239756 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	249 ms	239844 KB	Output is correct
2	Correct	240 ms	239844 KB	Output is correct
3	Correct	248 ms	239844 KB	Output is correct
4	Correct	233 ms	239844 KB	Output is correct
5	Correct	227 ms	239844 KB	Output is correct
6	Correct	258 ms	240256 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	185 ms	197112 KB	Output is correct
2	Correct	188 ms	197112 KB	Output is correct
3	Correct	186 ms	197112 KB	Output is correct
4	Correct	186 ms	197112 KB	Output is correct
5	Correct	186 ms	197112 KB	Output is correct
6	Correct	197 ms	197112 KB	Output is correct
7	Correct	192 ms	197112 KB	Output is correct
8	Correct	439 ms	202484 KB	Output is correct
9	Correct	437 ms	206872 KB	Output is correct
10	Correct	450 ms	210740 KB	Output is correct
11	Correct	455 ms	214676 KB	Output is correct
12	Correct	447 ms	215392 KB	Output is correct
13	Correct	506 ms	217812 KB	Output is correct
14	Correct	417 ms	223520 KB	Output is correct
15	Correct	532 ms	230584 KB	Output is correct
16	Correct	536 ms	236320 KB	Output is correct
17	Correct	454 ms	239756 KB	Output is correct
18	Correct	249 ms	239844 KB	Output is correct
19	Correct	240 ms	239844 KB	Output is correct
20	Correct	248 ms	239844 KB	Output is correct
21	Correct	233 ms	239844 KB	Output is correct
22	Correct	227 ms	239844 KB	Output is correct
23	Correct	258 ms	240256 KB	Output is correct
24	Correct	483 ms	247220 KB	Output is correct
25	Correct	506 ms	253092 KB	Output is correct
26	Correct	472 ms	254772 KB	Output is correct
27	Correct	517 ms	259200 KB	Output is correct
28	Correct	583 ms	274244 KB	Output is correct
29	Correct	435 ms	274244 KB	Output is correct

답안 #86577

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0