Submission #33396

#	Time	Username	Problem	Language	Result	Execution time	Memory
33396		aome	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	753 ms	746524 KiB

selling_rna

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

const int N = 100005;

typedef pair<int, int> ii;

int n, m;
string s[N];
vector<ii> go;

int to(char ch) {
	if (ch == 'A') return 0;
	if (ch == 'G') return 1;
	if (ch == 'C') return 2;
	if (ch == 'U') return 3;
}

struct Trie {
	struct Node {
		int nxt[4], cnt;

		Node () {
			memset(nxt, 0, sizeof nxt); cnt = 0;
		}
	};

	int TIME;
	vector<Node> tree;
	vector<int> st, ed;

	Trie() {
		tree.push_back(Node());
	}

	void update(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int tmp = to(s[i]);
			if (!tree[cur].nxt[tmp]) {
				tree[cur].nxt[tmp] = tree.size(), tree.push_back(Node());
			}
			cur = tree[cur].nxt[tmp], tree[cur].cnt++;
		}
	}

	int query(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int tmp = to(s[i]);
			if (!tree[cur].nxt[tmp]) return 0;
			cur = tree[cur].nxt[tmp];
		}
		return tree[cur].cnt;
	}

	void dfs(int u) {
		st[u] = ++TIME;
		for (int i = 0; i < 4; ++i) {
			if (tree[u].nxt[i]) dfs(tree[u].nxt[i]); 
		}
		ed[u] = TIME;
	}

	void cal() {
		TIME = 0, st.assign(tree.size(), 0), ed.assign(tree.size(), 0), dfs(0);
	}

	int findU(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int tmp = to(s[i]);
			cur = tree[cur].nxt[tmp];
		}
		return st[cur];
	}

	ii findQ(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int tmp = to(s[i]);
			if (!tree[cur].nxt[tmp]) return ii(0, 0);
			cur = tree[cur].nxt[tmp];
		}
		return ii(st[cur], ed[cur]);
	} 

} it[4 * N], pref;

void build(int i, int l, int r) {
	for (int j = l; j <= r; ++j) it[i].update(s[go[j].second]);
	if (l == r) return;	
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
}

int query(int i, int l, int r, int u, int v, string &s) {
	if (l > v || u > r) return 0;
	if (u <= l && r <= v) return it[i].query(s);
	int mid = (l + r) >> 1;
	return query(i << 1, l, mid, u, v, s) + query(i << 1 | 1, mid + 1, r, u, v, s);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> s[i], pref.update(s[i]);
	}
	pref.cal();
	for (int i = 0; i < n; ++i) {
		int tmp = pref.findU(s[i]);
		go.push_back(ii(tmp, i));
	}
	sort(go.begin(), go.end());
	for (int i = 0; i < n; ++i) {
		reverse(s[i].begin(), s[i].end());
	}
	build(1, 0, n - 1);
	for (int i = 0; i < m; ++i) {
		string p, q; cin >> p >> q;
		ii tmp = pref.findQ(p);
		if (!tmp.first) {
			printf("0\n"); continue;
		}
		int l = lower_bound(go.begin(), go.end(), ii(tmp.first, 0)) - go.begin();
		int r = lower_bound(go.begin(), go.end(), ii(tmp.second + 1, 0)) - go.begin() - 1;
		reverse(q.begin(), q.end());
		//cout << query(1, 0, n - 1, l, r, q) << '\n';
		printf("%d\n", query(1, 0, n - 1, l, r, q));
	}
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::update(std::__cxx11::string&)':
selling_rna.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); ++i) {
                     ^
selling_rna.cpp: In member function 'int Trie::query(std::__cxx11::string&)':
selling_rna.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); ++i) {
                     ^
selling_rna.cpp: In member function 'int Trie::findU(std::__cxx11::string&)':
selling_rna.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); ++i) {
                     ^
selling_rna.cpp: In member function 'ii Trie::findQ(std::__cxx11::string&)':
selling_rna.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); ++i) {
                     ^
selling_rna.cpp: In function 'int to(char)':
selling_rna.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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