oj.uz

Submission #86577

# Submission time Handle Problem Language Result Execution time Memory
86577 2018-11-26T17:01:54 Z KCSC Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 583 ms 274244 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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