Submission #717076

#	Time	Username	Problem	Language	Result	Execution time	Memory
717076		buidangnguyen05	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	192 ms	194248 KiB

selling_rna

//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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40