Submission #647417

#	Time	Username	Problem	Language	Result	Execution time	Memory
647417		ymm	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	277 ms	47432 KiB

selling_rna

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,abm,bmi,bmi2")

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'032;
const int S = 4096;

struct node
{
	bitset<S> *mask;
	int child[4];
} pool[50000000];

int rt_ltr, rt_rtl;

int new_node()
{
	static int nxt = 1;
	return nxt++;
}

int rna_to_int(char c)
{
	switch (c) {
	case 'A': return 0;
	case 'U': return 1;
	case 'C': return 2;
	case 'G': return 3;
	}
	return -1;
}

void trie_set(string s, int rt, int pos, int val)
{
	int t = rt;
	for (char c : s) {
		int x = rna_to_int(c);
		if (!pool[t].child[x])
			return;
		t = pool[t].child[x];
		if (pool[t].mask)
			(*pool[t].mask)[pos] = val;
	}
}

int trie_insert(string s, int rt)
{
	int t = rt;
	for (char c : s) {
		int x = rna_to_int(c);
		if (!pool[t].child[x])
			pool[t].child[x] = new_node();
		t = pool[t].child[x];
	}
	if (!pool[t].mask)
		pool[t].mask = new bitset<S>;
	return t;
}

string joi_rna[N], cus_pre[N], cus_suf[N];
int cus_pre_node[N], cus_suf_node[N];
int ans[N];
int n, m;

void set_joi_intrvl(int l, int r, int val)
{
	Loop (i,l,r) {
		trie_set(joi_rna[i], rt_ltr, i-l, val);
		reverse(joi_rna[i].begin(), joi_rna[i].end());
		trie_set(joi_rna[i], rt_rtl, i-l, val);
		reverse(joi_rna[i].begin(), joi_rna[i].end());
	}
}

int fast_bs_cnt(bitset<S> *a, bitset<S> *b)
{
	int *x = (int *)a;
	int *y = (int *)b;
	int ans = 0;
	Loop (i,0,S/8/sizeof(int))
		ans += __builtin_popcount(x[i] & y[i]);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		cin >> joi_rna[i];
	}
	Loop (i,0,m) {
		cin >> cus_pre[i];
		cin >> cus_suf[i];
		reverse(cus_suf[i].begin(), cus_suf[i].end());
	}
	rt_ltr = new_node();
	rt_rtl = new_node();
	Loop (i,0,m) {
		cus_pre_node[i] = trie_insert(cus_pre[i], rt_ltr);
		cus_suf_node[i] = trie_insert(cus_suf[i], rt_rtl);
	}
	for (int l = 0; l < n; l += S) {
		int r = min(l+S, n);
		set_joi_intrvl(l, r, 1);
		Loop (cus,0,m) {
			auto m1 = pool[cus_pre_node[cus]].mask;
			auto m2 = pool[cus_suf_node[cus]].mask;
			ans[cus] += fast_bs_cnt(m1, m2);
			//ans[cus] += (*m1 & *m2).count();
		}
		set_joi_intrvl(l, r, 0);
	}
	Loop (i,0,m)
		cout << ans[i] << '\n';
}

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