oj.uz

Submission #35355

# Submission time Handle Problem Language Result Execution time Memory
35355 2017-11-20T15:38:23 Z cheater2k Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 486 ms 802328 KB 
#include <bits/stdc++.h>
using namespace std;

int id(char c) {
	if (c == 'A') return 0;
	else if (c == 'G') return 1;
	else if (c == 'C') return 2;
	else return 3;
}

const int N = 100010;
typedef pair<int,int> ii;

int TIME;
struct Trie {
	struct Node {
		int ch[4]; int f;
		Node() { memset(ch, -1, sizeof ch); f = 0; }
	};
	vector<Node> tr;
	vector<int> tin, tout;
	void init() { tr.clear(); tin.clear(); tout.clear(); tr.push_back(Node()); }

	void add(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int ID = id(s[i]);
			if (tr[cur].ch[ID] == -1) {
				tr[cur].ch[ID] = tr.size(), tr.push_back(Node());
			}
			cur = tr[cur].ch[ID];
			tr[cur].f++;
		}
	} 

	void dfs(int u) {
		tin[u] = ++TIME;
		for (int i = 0; i < 4; ++i) if (tr[u].ch[i] != -1) dfs(tr[u].ch[i]);
		tout[u] = TIME;
	}

	void prepare() {
		tin.assign(tr.size(), 0); tout.assign(tr.size(), 0); dfs(0);
	}

	ii get_pos(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int ID = id(s[i]);
			if (tr[cur].ch[ID] == -1) return ii(-1,-1);
			cur = tr[cur].ch[ID];
		}
		return ii(tin[cur], tout[cur]);
	}

	int query(string &s) {
		int cur = 0;
		for (int i = 0; i < s.size(); ++i) {
			int ID = id(s[i]);
			if (tr[cur].ch[ID] == -1) return 0;
			cur = tr[cur].ch[ID];
		}
		return tr[cur].f;
	}
} it[N << 2], pref;

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

#define mid ((l + r) >> 1)
void build(int v, int l, int r) {
	it[v].init();
	for (int i = l; i <= r; ++i) {
		for (int j : vec[i]) it[v].add(s[j]);
	}
	if (l == r) return;
	build(v << 1, l, mid); build(v << 1 | 1, mid + 1, r);
}

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	pref.init();
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		pref.add(s[i]);
	}
	pref.prepare();
	
	for (int i = 1; i <= n; ++i) {
		int pos = pref.get_pos(s[i]).first;
		vec[pos].push_back(i);
	}

	for (int i = 1; i <= n; ++i) reverse(s[i].begin(), s[i].end());
	build(1, 1, TIME);
	
	string p, q;
	while(m--) {
		cin >> p >> q;
		ii P = pref.get_pos(p);
		if (P.first == -1 && P.second == -1) {
			printf("0\n"); continue;
		}
		reverse(q.begin(), q.end());
		int res = get(1, 1, TIME, P.first, P.second, q);
		printf("%d\n", res);
	}
}

Compilation message

selling_rna.cpp: In member function 'void Trie::add(std::__cxx11::string&)':
selling_rna.cpp:26: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::get_pos(std::__cxx11::string&)':
selling_rna.cpp:48: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:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); ++i) {
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35776 KB Output is correct
2 Correct 19 ms 35776 KB Output is correct
3 Correct 9 ms 35776 KB Output is correct
4 Correct 13 ms 35776 KB Output is correct
5 Correct 9 ms 35776 KB Output is correct
6 Correct 9 ms 35776 KB Output is correct
7 Correct 13 ms 35776 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 802328 KB Output is correct
2 Correct 486 ms 792676 KB Output is correct
3 Runtime error 99 ms 98316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36160 KB Output is correct
2 Correct 46 ms 37740 KB Output is correct
3 Correct 46 ms 37044 KB Output is correct
4 Correct 29 ms 35916 KB Output is correct
5 Correct 53 ms 37560 KB Output is correct
6 Correct 46 ms 37060 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35776 KB Output is correct
2 Correct 19 ms 35776 KB Output is correct
3 Correct 9 ms 35776 KB Output is correct
4 Correct 13 ms 35776 KB Output is correct
5 Correct 9 ms 35776 KB Output is correct
6 Correct 9 ms 35776 KB Output is correct
7 Correct 13 ms 35776 KB Output is correct
8 Correct 453 ms 802328 KB Output is correct
9 Correct 486 ms 792676 KB Output is correct
10 Runtime error 99 ms 98316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -