Submission #86575

#	Time	Username	Problem	Language	Result	Execution time	Memory
86575		KCSC	Selling RNA Strands (JOI16_selling_rna)	C++11	0 / 100	353 ms	108192 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];
	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];

void insert(Node trie[], int &tot, int nd, int ps, string &str) {
	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); } }
		
void dfs(Node trie[], int &tot, int nd) {
	for (int i = 0; i < 4; ++i) {
		if (trie[nd].nxt[i] != 0) {
			dfs(trie, tot, trie[nd].nxt[i]);
			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); } }
	if (trie[nd].mn == INF) {
		trie[nd].mn = trie[nd].mx = ++tot; } }

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]); insert(trie2, nr2, 1, 0, rev[i]); }
	int nr; nr = 0; dfs(trie1, nr, 1); nr = 0; dfs(trie2, nr, 1);
	for (int i = 1; i <= n; ++i) {
		_mn = INF; _mx = -INF; getMinMax(trie1, 1, 0, str[i]); int ps1 = _mn;
		_mn = INF; _mx = -INF; getMinMax(trie2, 1, 0, rev[i]); int ps2 = _mn;
		evn[ps1].push_back(Event(0, make_pair(ps2, ps2))); }
	for (int i = 1; i <= m; ++i) {
		string str1, str2; cin >> str1 >> str2; 
		changeString(str1); changeString(str2); reverse(str2.begin(), str2.end());
		_mn = INF; _mx = -INF; getMinMax(trie1, 1, 0, str1); sgx[i] = make_pair(_mn, _mx);
		_mn = INF; _mx = -INF; 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 = 1; 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 (stderr)

selling_rna.cpp: In function 'void insert(Node*, int&, int, int, std::__cxx11::string&)':
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); } }
                                         ^
selling_rna.cpp: In function 'void getMinMax(Node*, int, int, std::__cxx11::string&)':
selling_rna.cpp:42:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ps == str.length()) {
      ~~~^~~~~~~~~~~~~~~
selling_rna.cpp:45:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (!trie[nd].nxt[str[ps]]) {
                            ^
selling_rna.cpp:48:40: warning: array subscript has type 'char' [-Wchar-subscripts]
    getMinMax(trie, trie[nd].nxt[str[ps]], ps + 1, str); } } } 
                                        ^

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