Submission #1138536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138536		SmuggingSpun	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	401 ms	145988 KiB

selling_rna

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
int n, m;
namespace sub12{
	const int mod = 1e9 + 33;
	const int base = 397;
	const int lim = 5e3 + 5;
	const int LIM = 2e6 + 5;
	int pw[LIM];
	vector<int>hash[lim];
	int get_hash(int id, int l, int r){
		return (ll(hash[id][r]) - 1LL * hash[id][l - 1] * pw[r - l + 1] + 1LL * mod * mod) % mod;
	}
	void solve(){
		for(int i = pw[0] = 1; i < LIM; i++){
			pw[i] = 1LL * pw[i - 1] * base % mod;
		}
		for(int i = 0; i < n; i++){
			string s;
			cin >> s;
			hash[i].emplace_back(0);
			for(int j = 0; j < s.size(); j++){
				hash[i].emplace_back((1LL * hash[i].back() * base + s[j]) % mod);
			}
		}
		for(int _ = 0; _ < m; _++){
			string p, q;
			cin >> p >> q;
			int ans = 0, P = 0, Q = 0;
			for(int i = 0; i < p.size(); i++){
				P = (1LL * P * base + p[i]) % mod;
			}
			for(int i = 0; i < q.size(); i++){
				Q = (1LL * Q * base + q[i]) % mod;
			}
			for(int i = 0; i < n; i++){
				if(hash[i].size() > max(p.size(), q.size()) && get_hash(i, 1, p.size()) == P && get_hash(i, int(hash[i].size()) - int(q.size()), int(hash[i].size()) - 1) == Q){
					ans++;
				}
			}
			cout << ans << "\n";
		}
	}
}
namespace sub34{
	const int LIM = 2e6 + 5;
	const int lim = 2e5 + 5;
	void convert(string& s){
		for(char& c : s){
			if(c == 'A'){
				c = 0;
			}
			else if(c == 'G'){
				c = 1;
			}
			else if(c == 'C'){
				c = 2;
			}
			else{
				c = 3;
			}
		}
	}
	struct Node{
		int child[4];
		Node(){
			memset(child, -1, sizeof(child));
		}	
	};
	struct Trie{
		vector<Node>trie;
		int time_dfs, low[LIM], tail[LIM];
		Trie(){
			time_dfs = 0;
			trie.emplace_back(Node());
		}
		void insert(string& s){
			int root = 0;
			for(char& c : s){
				if(trie[root].child[c] == -1){
					trie[root].child[c] = trie.size();
					trie.emplace_back(Node());
				}
				root = trie[root].child[c];
			}
		}
		void dfs(int s){
			low[s] = ++time_dfs;
			for(int i = 0; i < 4; i++){
				if(trie[s].child[i] != -1){
					dfs(trie[s].child[i]);
				}
			}
			tail[s] = time_dfs;
		}
		pair<int, int>get_pair(string& s){
			int root = 0;
			for(char& c : s){
				if(trie[root].child[c] == -1){
					return make_pair(-1, -1);
				}
				root = trie[root].child[c];
			}
			return make_pair(low[root], tail[root]);
		}
	};
	Trie prefix, suffix;
	int bit[LIM], ans[lim];
	vector<pair<int, int>>query[LIM];
	vector<int>point[LIM];
	void update(int p){
		for(; p < LIM; p += p & -p){
			bit[p]++;
		}
	}
	int get(int p){
		int ans = 0;
		for(; p > 0; p -= p & -p){
			ans += bit[p];
		}
		return ans;
	}
	void solve(){
		vector<string>S(n);
		for(string& s : S){
			cin >> s;
			convert(s);
			prefix.insert(s);
			reverse(s.begin(), s.end());
			suffix.insert(s);
		}
		prefix.dfs(0);
		suffix.dfs(0);
		for(int i = 0; i < n; i++){
			int y = suffix.get_pair(S[i]).first;
			reverse(S[i].begin(), S[i].end());
			point[y].emplace_back(prefix.get_pair(S[i]).first);
		}
		for(int i = 1; i <= m; i++){
			string p, q;
			cin >> p >> q;
			convert(p);
			reverse(q.begin(), q.end());
			convert(q);
			pair<int, int>range_prefix = prefix.get_pair(p), range_suffix = suffix.get_pair(q);
			if(range_prefix.first != -1 && range_suffix.first != -1){
				query[range_suffix.second].emplace_back(range_prefix.second, i);
				query[range_suffix.first - 1].emplace_back(range_prefix.first - 1, i);
				query[range_suffix.second].emplace_back(range_prefix.first - 1, -i);
				query[range_suffix.first - 1].emplace_back(range_prefix.second, -i);
			}
		}
		memset(ans, 0, sizeof(ans));
		memset(bit, 0, sizeof(bit));
		for(int i = 1; i < LIM; i++){
			for(int& j : point[i]){
				update(j);
			}
			for(auto& [j, index] : query[i]){
				if(index < 0){
					ans[-index] -= get(j);
				}
				else{
					ans[index] += get(j);
				}
			}
		}
		for(int i = 1; i <= m; i++){
			cout << ans[i] << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	if(max(n, m) <= 5000){
		sub12::solve();
	}
	else{
		sub34::solve();
	}
}

Compilation message (stderr)

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

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