Submission #1282448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282448		KickingKun	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	179 ms	188440 KiB

selling_rna

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

#define ll long long
#define ld long double
#define emb emplace_back
#define pii pair <int, int>
#define fi first
#define se second

#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))

#define Task "rna"

template <class T> bool minimize(T &a, T b) {
	if (a > b) return a = b, true;
	return false;
}

template <class T> bool maximize(T &a, T b) {
	if (a < b) return a = b, true;
	return false;
}

const int N = 1e5 + 5, mod = 1e9 + 321, base = 311;
const ll INF = 1e18;

const int root = 0;
int cntNode = 0;

struct Node {
	int child[4], cnt;
	Node () {
		memset(child, -1, sizeof child);
		cnt = 0;
	}
} node[N * 20 * 4];

void add(string &str) {
	int p = root;
	for (char c: str) {
		int k = c - 'A';
		if (node[p].child[c] == -1)
			node[p].child[c] = ++cntNode;
		p = node[p].child[c]; ++node[p].cnt;
	}
}

int get(string &str) {
	int p = root;
	for (char c: str) {
		int k = c - 'A';
		if (node[p].child[c] == -1) return 0;
		p = node[p].child[c];
	}
	return node[p].cnt;
}

int n, m;
string s[N], r[N];
string p[N], q[N];
vector <tuple <string, int, int>> query[N];

string decode(string str) {
	for (char &c: str) {
		if (c == 'C') c = 'B';
		else if (c == 'G') c = 'C';
		else if (c == 'U') c = 'D'; 
	}
	return str;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	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]; s[i] = decode(s[i]);
	}
	
	sort (s + 1, s + n + 1);
	for (int i = 1; i <= n; i++) {
		r[i] = s[i]; reverse(r[i].begin(), r[i].end());
	}
	
	int outID = n + 1;
	for (int i = 0; i < m; i++) {
		cin >> p[i] >> q[i];
		p[i] = decode(p[i]); q[i] = decode(q[i]);
		reverse(q[i].begin(), q[i].end());
		
		int L = lower_bound(s + 1, s + n + 1, p[i]) - s;
		int R = upper_bound(s + L, s + n + 1, p[i] + 'z') - s - 1;
		
		if (L <= R) {
			query[L - 1].emb(q[i], i, -1);
			query[R].emb(q[i], i, 1);
		}
		
//		cerr << L << ' ' << R << '\n';
	}
	
	vector <int> ans(m);
	for (int i = 1; i <= n; i++) {
		add(r[i]);
		for (int _ = 0; _ < query[i].size(); _++) {
			string &q = get<0>(query[i][_]);
			int id = get<1>(query[i][_]), b = get<2>(query[i][_]);
			ans[id] += b * get(q);
		}
	}
	
	for (int x: ans) cout << x << '\n';
}

Compilation message (stderr)

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

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