oj.uz

Submission #35356

# Submission time Handle Problem Language Result Execution time Memory
35356 2017-11-20T15:56:00 Z cheater2k Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 709 ms 731120 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<ii> vec;
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) it[v].add(s[vec[i].second]);
	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.push_back(ii(pos, i));
	}
	sort(vec.begin(), vec.end());

	for (int i = 1; i <= n; ++i) reverse(s[i].begin(), s[i].end());
	build(1, 0, n - 1);
	
	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());
		P.first = lower_bound(vec.begin(), vec.end(), ii(P.first, 0)) - vec.begin();
		P.second = upper_bound(vec.begin(), vec.end(), ii(P.second, 1e9)) - vec.begin() - 1;
		int res = get(1, 0, n - 1, 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 33436 KB Output is correct
2 Correct 6 ms 33436 KB Output is correct
3 Correct 13 ms 33436 KB Output is correct
4 Correct 3 ms 33436 KB Output is correct
5 Correct 6 ms 33436 KB Output is correct
6 Correct 3 ms 33436 KB Output is correct
7 Correct 3 ms 33436 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 690480 KB Output is correct
2 Correct 523 ms 731120 KB Output is correct
3 Correct 453 ms 272504 KB Output is correct
4 Correct 446 ms 263140 KB Output is correct
5 Correct 513 ms 603924 KB Output is correct
6 Correct 529 ms 606528 KB Output is correct
7 Correct 186 ms 119144 KB Output is correct
8 Correct 426 ms 528472 KB Output is correct
9 Correct 369 ms 474876 KB Output is correct
10 Correct 353 ms 383328 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 43356 KB Output is correct
2 Correct 69 ms 42928 KB Output is correct
3 Correct 76 ms 42812 KB Output is correct
4 Correct 76 ms 40188 KB Output is correct
5 Correct 73 ms 41676 KB Output is correct
6 Correct 96 ms 42196 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33436 KB Output is correct
2 Correct 6 ms 33436 KB Output is correct
3 Correct 13 ms 33436 KB Output is correct
4 Correct 3 ms 33436 KB Output is correct
5 Correct 6 ms 33436 KB Output is correct
6 Correct 3 ms 33436 KB Output is correct
7 Correct 3 ms 33436 KB Output is correct
8 Correct 463 ms 690480 KB Output is correct
9 Correct 523 ms 731120 KB Output is correct
10 Correct 453 ms 272504 KB Output is correct
11 Correct 446 ms 263140 KB Output is correct
12 Correct 513 ms 603924 KB Output is correct
13 Correct 529 ms 606528 KB Output is correct
14 Correct 186 ms 119144 KB Output is correct
15 Correct 426 ms 528472 KB Output is correct
16 Correct 369 ms 474876 KB Output is correct
17 Correct 353 ms 383328 KB Output is correct
18 Correct 89 ms 43356 KB Output is correct
19 Correct 69 ms 42928 KB Output is correct
20 Correct 76 ms 42812 KB Output is correct
21 Correct 76 ms 40188 KB Output is correct
22 Correct 73 ms 41676 KB Output is correct
23 Correct 96 ms 42196 KB Output is correct
24 Correct 486 ms 698880 KB Output is correct
25 Correct 543 ms 703108 KB Output is correct
26 Correct 556 ms 691524 KB Output is correct
27 Correct 539 ms 257012 KB Output is correct
28 Correct 709 ms 252268 KB Output is correct
29 Correct 473 ms 100244 KB Output is correct