oj.uz

Submission #870404

# Submission time Handle Problem Language Result Execution time Memory
870404 2023-11-07T18:38:52 Z serifefedartar Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 621 ms 504652 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 100;

int no[MAXN];
int last_given = 0;

struct Node {
	Node *to[4];
	vector<int> v;
	vector<int> last;
	void srt() {
		sort(v.begin(), v.end());
		for (int i = 0; i < 4; i++) {
			if (to[i] != NULL)
				to[i]->srt();
		}
	}
	void dfs() {
		for (auto u : last) {
			last_given++;
			no[u] = last_given;
		}

		for (int i = 0; i < 4; i++) {
			if (to[i] != NULL)
				to[i]->dfs();
		}
	}
};

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

vector<string> vs;
int main() {
	int N, M;
	cin >> N >> M;

	Node *root = new Node();
	Node *root_rev = new Node();
	vs = vector<string>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> vs[i];

		Node *now = root;
		now->v.push_back(i);
		for (auto u : vs[i]) {
			int q = c(u);
			if (now->to[q] == NULL)
				now->to[q] = new Node();
			now = now->to[q];
			now->v.push_back(i);
		}
		now->last.push_back(i);
	}
	root->dfs();

	for (int i = 1; i <= N; i++) {
		int q = no[i];
		Node *now = root_rev;
		now->v.push_back(q);

		int len = vs[i].length();
		for (int j = len-1; j >= 0; j--) {
			int p = c(vs[i][j]);
			if (now->to[p] == NULL)
				now->to[p] = new Node();
			now = now->to[p];
			now->v.push_back(q);
		}
	}

	root = new Node();
	for (int i = 1; i <= N; i++) {
		int q = no[i];
		Node *now = root;
		now->v.push_back(q);
		for (auto u : vs[i]) {
			int p = c(u);
			if (now->to[p] == NULL)
				now->to[p] = new Node();
			now = now->to[p];
			now->v.push_back(q);
		}
	}
	root->srt();
	root_rev->srt();

	while (M--) {
		string pref, suff;
		cin >> pref >> suff;
		reverse(suff.begin(), suff.end());

		Node *now = root;
		for (auto u : pref) {
			int q = c(u);
			if (now->to[q] == NULL)
				now->to[q] = new Node();
			now = now->to[q];
		}

		int mn = -1, mx = -1;
		if (now->v.size()) {
			mn = now->v.front();
			mx = now->v.back();
		}

		now = root_rev;
		for (auto u : suff) {
			int q = c(u);
			if (now->to[q] == NULL)
				now->to[q] = new Node();
			now = now->to[q];
		}
		cout << upper_bound(now->v.begin(), now->v.end(), mx) - lower_bound(now->v.begin(), now->v.end(), mn) << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 277768 KB Output is correct
2 Correct 387 ms 263444 KB Output is correct
3 Correct 578 ms 504652 KB Output is correct
4 Correct 551 ms 480540 KB Output is correct
5 Correct 493 ms 462128 KB Output is correct
6 Correct 518 ms 469392 KB Output is correct
7 Correct 162 ms 33680 KB Output is correct
8 Correct 496 ms 295204 KB Output is correct
9 Correct 467 ms 248912 KB Output is correct
10 Correct 379 ms 242376 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5248 KB Output is correct
2 Correct 62 ms 4792 KB Output is correct
3 Correct 91 ms 5060 KB Output is correct
4 Correct 82 ms 4052 KB Output is correct
5 Correct 65 ms 4952 KB Output is correct
6 Correct 80 ms 5324 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 382 ms 277768 KB Output is correct
9 Correct 387 ms 263444 KB Output is correct
10 Correct 578 ms 504652 KB Output is correct
11 Correct 551 ms 480540 KB Output is correct
12 Correct 493 ms 462128 KB Output is correct
13 Correct 518 ms 469392 KB Output is correct
14 Correct 162 ms 33680 KB Output is correct
15 Correct 496 ms 295204 KB Output is correct
16 Correct 467 ms 248912 KB Output is correct
17 Correct 379 ms 242376 KB Output is correct
18 Correct 96 ms 5248 KB Output is correct
19 Correct 62 ms 4792 KB Output is correct
20 Correct 91 ms 5060 KB Output is correct
21 Correct 82 ms 4052 KB Output is correct
22 Correct 65 ms 4952 KB Output is correct
23 Correct 80 ms 5324 KB Output is correct
24 Correct 431 ms 231492 KB Output is correct
25 Correct 450 ms 231764 KB Output is correct
26 Correct 386 ms 229056 KB Output is correct
27 Correct 621 ms 415100 KB Output is correct
28 Correct 473 ms 69404 KB Output is correct
29 Correct 301 ms 24160 KB Output is correct