oj.uz

Submission #33392

# Submission time Handle Problem Language Result Execution time Memory
33392 2017-10-25T09:38:08 Z aome Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 916 ms 1048576 KB 
#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;
	};

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

	Trie() {
		tree.push_back(Node()), st.push_back(0), ed.push_back(0);
	}

	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());
				st.push_back(0), ed.push_back(0);
			}
			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;
	}

	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.dfs(0);
	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) {
			cout << "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';
	}
}

Compilation message

selling_rna.cpp: In member function 'void Trie::update(std::__cxx11::string&)':
selling_rna.cpp:34: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:46: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:64: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:73: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 74032 KB Output is correct
2 Correct 76 ms 74164 KB Output is correct
3 Correct 79 ms 74164 KB Output is correct
4 Correct 79 ms 74032 KB Output is correct
5 Correct 79 ms 74164 KB Output is correct
6 Correct 66 ms 74032 KB Output is correct
7 Correct 73 ms 74032 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 995412 KB Output is correct
2 Memory limit exceeded 916 ms 1048576 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 83984 KB Execution timed out (wall clock limit exceeded)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 74032 KB Output is correct
2 Correct 76 ms 74164 KB Output is correct
3 Correct 79 ms 74164 KB Output is correct
4 Correct 79 ms 74032 KB Output is correct
5 Correct 79 ms 74164 KB Output is correct
6 Correct 66 ms 74032 KB Output is correct
7 Correct 73 ms 74032 KB Output is correct
8 Correct 849 ms 995412 KB Output is correct
9 Memory limit exceeded 916 ms 1048576 KB Memory limit exceeded
10 Halted 0 ms 0 KB -