Submission #1222083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222083		mingga	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	255 ms	308224 KiB

selling_rna

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 1e5 + 7;
const int M = 2e6 + 7;
int n, m;
string s[N];

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

struct Trie {
	struct Node {
		int child[4];
		vector<int> vec;
		Node() {
			memset(child, -1, sizeof child);
		}
	} nodes[M];
	int cur = 0;
	int new_node() {
		nodes[++cur] = Node();
		return cur;
	}
	Trie() {}
	void add(string s, int id) {
		int p = 0;
		for(auto u : s) {
			int x = get_id(u);
			if(nodes[p].child[x] == -1) nodes[p].child[x] = new_node();
			p = nodes[p].child[x];
			nodes[p].vec.pb(id);
		}
	}
	pair<int, int> get_range(string s) {
		int p = 0;
		for(auto u : s) {
			int x = get_id(u);
			if(nodes[p].child[x] == -1) return {-1, -1};
			p = nodes[p].child[x];
		}
		return {nodes[p].vec[0], nodes[p].vec.back()};
	}
	int query(string s, int mn, int mx) {
		int p = 0;
		for(auto u : s) {
			int x = get_id(u);
			if(nodes[p].child[x] == -1) return 0;
			p = nodes[p].child[x];
		}
		return upper_bound(all(nodes[p].vec), mx) - lower_bound(all(nodes[p].vec), mn);
	}
} tri, suf_tri;

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> s[i];
	sort(s + 1, s + n + 1);
	for(int i = 1; i <= n; i++) {
		tri.add(s[i], i);
		string r = s[i];
		reverse(all(r));
		suf_tri.add(r, i);
	}
	for(int i = 1; i <= m; i++) {
		string p, q; cin >> p >> q;
		reverse(all(q));
		pair<int, int> dak = tri.get_range(p);
		if(dak.fi == -1) cout << 0 << ln;
		else {
			cout << suf_tri.query(q, dak.fi, dak.se) << ln;
		}
	}
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:73:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:74:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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