Submission #1261529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261529		Bui_Quoc_Cuong	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	206 ms	238788 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
const int N = 3e5 + 5;

map <char, int> code;

int n, q;
string prefix[N], suffix[N];
int ID[N];

struct PrefixTrie {
	struct Node{
		Node *child[5];
		int min_id, max_id;
		Node() {
			min_id = 2e9;
			max_id = - 2e9;
			FOR(i, 1, 4) child[i] = NULL;
		}
	};
	Node *root = new Node();
	void addString (const string &s, int id) {
		Node *p = root;
		for (const char &c : s) {
			int j = code[c];
			if (p -> child[j] == NULL) p -> child[j] = new Node();
			p = p -> child[j];
			p -> min_id = min(p -> min_id, id);
			p -> max_id = max(p -> max_id, id);
		}
	}
	pair <int, int> get (const string &s) {
		Node *p = root;
		for (const char &c : s) {
			int j = code[c];
			if (p -> child[j] == NULL) return make_pair(- 1, - 1);
			p = p -> child[j];
		}
		return make_pair(p -> min_id, p -> max_id);
	}
} Trie1;

struct SuffixTrie {
	struct Node{
		Node *child[5];
		vector <int> id;
		Node() {
			id.clear();
			FOR(i, 1, 4) child[i] = NULL;
		}
	};
	Node *root = new Node();
	void addString (const string &s, int id) {
		Node *p = root;
		for (const char &c : s) {
			int j = code[c];
			if (p -> child[j] == NULL) p -> child[j] = new Node();
			p = p -> child[j];
			p -> id.push_back(id);
		}
	}
	int get (const string &s, int L, int R) {
		if (L == - 1 || R == - 1) return 0;
		Node *p = root;
		for (const char &c : s) {
			int j = code[c];
			if (p -> child[j] == NULL) return 0;
			p = p -> child[j];
		}	
		return upper_bound(p -> id.begin(), p -> id.end(), R) - lower_bound(p -> id.begin(), p -> id.end(), L);
	}
} Trie2;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define ko "kieuoanh"
    if (fopen(ko".inp", "r")) { 
        freopen(ko".inp", "r", stdin); 
        freopen(ko".out", "w", stdout);
    }
    cin >> n >> q;
    code['A'] = 1;
    code['U'] = 2;
    code['G'] = 3;
    code['C'] = 4;
    FOR(i, 1, n) {
    	cin >> prefix[i];
    	suffix[i] = prefix[i];
    	reverse(suffix[i].begin(), suffix[i].end());
    	ID[i] = i;
    }
    sort(ID + 1, ID + 1 + n, [&] (int x, int y) {
    	return prefix[x] < prefix[y];
    });
    FOR(i, 1, n) {
    	Trie1.addString(prefix[ID[i]], i);
    	Trie2.addString(suffix[ID[i]], i);
    }
    while (q--) {
    	string P, Q; cin >> P >> Q;
    	pair <int, int> tam = Trie1.get(P);
    	reverse(Q.begin(), Q.end());
    	cout << Trie2.get(Q, tam.first, tam.second) << "\n";
    }
    cerr << "\n[Time Elapsed] " << 0.001 * clock() << "s\n";
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40