oj.uz

Submission #647417

# Submission time Handle Problem Language Result Execution time Memory
647417 2022-10-02T13:22:48 Z ymm Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 277 ms 47432 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9736 KB Output is correct
2 Correct 7 ms 9736 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 18744 KB Output is correct
2 Correct 67 ms 18460 KB Output is correct
3 Correct 59 ms 18472 KB Output is correct
4 Correct 73 ms 18444 KB Output is correct
5 Correct 56 ms 41292 KB Output is correct
6 Correct 54 ms 40924 KB Output is correct
7 Correct 95 ms 22476 KB Output is correct
8 Correct 89 ms 47432 KB Output is correct
9 Correct 89 ms 46164 KB Output is correct
10 Correct 51 ms 16900 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10988 KB Output is correct
2 Correct 36 ms 10608 KB Output is correct
3 Correct 50 ms 10752 KB Output is correct
4 Correct 36 ms 10704 KB Output is correct
5 Correct 33 ms 10604 KB Output is correct
6 Correct 47 ms 10804 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9736 KB Output is correct
2 Correct 7 ms 9736 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 56 ms 18744 KB Output is correct
9 Correct 67 ms 18460 KB Output is correct
10 Correct 59 ms 18472 KB Output is correct
11 Correct 73 ms 18444 KB Output is correct
12 Correct 56 ms 41292 KB Output is correct
13 Correct 54 ms 40924 KB Output is correct
14 Correct 95 ms 22476 KB Output is correct
15 Correct 89 ms 47432 KB Output is correct
16 Correct 89 ms 46164 KB Output is correct
17 Correct 51 ms 16900 KB Output is correct
18 Correct 67 ms 10988 KB Output is correct
19 Correct 36 ms 10608 KB Output is correct
20 Correct 50 ms 10752 KB Output is correct
21 Correct 36 ms 10704 KB Output is correct
22 Correct 33 ms 10604 KB Output is correct
23 Correct 47 ms 10804 KB Output is correct
24 Correct 65 ms 18600 KB Output is correct
25 Correct 69 ms 19388 KB Output is correct
26 Correct 71 ms 18424 KB Output is correct
27 Correct 66 ms 18644 KB Output is correct
28 Correct 277 ms 21080 KB Output is correct
29 Correct 222 ms 14576 KB Output is correct