oj.uz

Submission #717076

# Submission time Handle Problem Language Result Execution time Memory
717076 2023-04-01T04:03:30 Z buidangnguyen05 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 192 ms 194248 KB 
//source: 

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

typedef long long ll;

inline int get(const char &c) {
	if (c == 'A') return 0;
	if (c == 'G') return 1;
	if (c == 'C') return 2;
	return 3;
}

struct Trie {
	Trie* child[4];

	int mx, mi;

	Trie () {
		child[0] = child[1] = child[2] = child[3] = nullptr;
		mx = 0, mi = 1e9;
	}
};

Trie *root = new Trie();

void add(const string &s, int idx) {
	Trie *p = root;
	for (const char &i : s) {
		int x = get(i);
		if (!p -> child[x]) p -> child[x] = new Trie();
		p = p -> child[x];

		p -> mx = max(p -> mx, idx);
		p -> mi = min(p -> mi, idx);
	}
}

pair<int, int> get(const string &s) {
	Trie *p = root;
	for (const char &i : s) {
		int x = get(i);
		if (!p -> child[x]) return make_pair(-1, 0);
		p = p -> child[x];
	}
	return make_pair(p -> mi, p -> mx);
}

struct RevTrie {
	RevTrie* child[4];

	vector<int> pos;

	RevTrie () {
		child[0] = child[1] = child[2] = child[3] = nullptr;
	}
};

RevTrie *RevRoot = new RevTrie();

void RevAdd(const string &s, int idx) {
	RevTrie *p = RevRoot;
	for (const char &i : s) {
		int x = get(i);
		if (!p -> child[x]) p -> child[x] = new RevTrie();
		p = p -> child[x];

		p -> pos.push_back(idx);
	}
}

int get(const string &s, int L, int R) {
	RevTrie *p = RevRoot;
	for (const char &i : s) {
		int x = get(i);
		if (!p -> child[x]) return 0;
		p = p -> child[x];
	}

	return upper_bound(p -> pos.begin(), p -> pos.end(), R) - lower_bound(p -> pos.begin(), p -> pos.end(), L);
}

const int N = 1e5 + 10;
string a[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("JOI16_selling_rna.inp", "r")) {
		freopen("JOI16_selling_rna.inp", "r", stdin);
		freopen("JOI16_selling_rna.out", "w", stdout);
	}

	#ifdef LOCAL_MACHINE 
		if (fopen("task.inp", "r")) {
			freopen("task.inp", "r", stdin);
			freopen("task.out", "w", stdout);
		}
	#endif

	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> a[i];

	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) add(a[i], i);
	for (int i = 1; i <= n; ++i) reverse(a[i].begin(), a[i].end());
	for (int i = 1; i <= n; ++i) RevAdd(a[i], i);

	while (q--) {
		string P, Q; cin >> P >> Q;
		int L, R; tie(L, R) = get(P);
		if (!~L) {
			cout << "0\n";
			continue;
		}
		reverse(Q.begin(), Q.end());
		cout << get(Q, L, R) << "\n";
	}
}

// ඞඞඞඞඞ you sus

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:90:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   freopen("JOI16_selling_rna.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:91:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   freopen("JOI16_selling_rna.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 194248 KB Output is correct
2 Correct 191 ms 184308 KB Output is correct
3 Correct 123 ms 111984 KB Output is correct
4 Correct 122 ms 106960 KB Output is correct
5 Correct 172 ms 178676 KB Output is correct
6 Correct 176 ms 181324 KB Output is correct
7 Correct 49 ms 19020 KB Output is correct
8 Correct 165 ms 117980 KB Output is correct
9 Correct 143 ms 101320 KB Output is correct
10 Correct 107 ms 96196 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4680 KB Output is correct
2 Correct 19 ms 4816 KB Output is correct
3 Correct 22 ms 4704 KB Output is correct
4 Correct 18 ms 4436 KB Output is correct
5 Correct 19 ms 4728 KB Output is correct
6 Correct 23 ms 4712 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3460 KB Output is correct
4 Correct 3 ms 3452 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 184 ms 194248 KB Output is correct
9 Correct 191 ms 184308 KB Output is correct
10 Correct 123 ms 111984 KB Output is correct
11 Correct 122 ms 106960 KB Output is correct
12 Correct 172 ms 178676 KB Output is correct
13 Correct 176 ms 181324 KB Output is correct
14 Correct 49 ms 19020 KB Output is correct
15 Correct 165 ms 117980 KB Output is correct
16 Correct 143 ms 101320 KB Output is correct
17 Correct 107 ms 96196 KB Output is correct
18 Correct 23 ms 4680 KB Output is correct
19 Correct 19 ms 4816 KB Output is correct
20 Correct 22 ms 4704 KB Output is correct
21 Correct 18 ms 4436 KB Output is correct
22 Correct 19 ms 4728 KB Output is correct
23 Correct 23 ms 4712 KB Output is correct
24 Correct 179 ms 160512 KB Output is correct
25 Correct 192 ms 160672 KB Output is correct
26 Correct 181 ms 158788 KB Output is correct
27 Correct 118 ms 94408 KB Output is correct
28 Correct 142 ms 38552 KB Output is correct
29 Correct 63 ms 11860 KB Output is correct