Submission #1183416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183416		catch_me_if_you_can	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	190 ms	101364 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e6+2e3;

array<int, 4> ch[2][MX]; int Nn[2];

int cnt[2][MX]; int lb[2][MX];

map<char, int> con;

void pre()
{
	con['A'] = 0;
	con['G'] = 1;
	con['C'] = 2;
	con['U'] = 3;
	ch[0][0] = ch[1][0] = {-1, -1, -1, -1};
	return;
}

int create(int k)
{
	Nn[k]++;
	ch[k][Nn[k]] = {-1, -1, -1, -1};
	return Nn[k];
}

void add(const string &s, int k, int LABEL)
{
	int u = 0;
	for(auto c: s)
	{
		if(ch[k][u][con[c]] == -1)
			ch[k][u][con[c]] = create(k);
		u = ch[k][u][con[c]];
	}
	cnt[k][u]++;
	lb[k][u] = LABEL;
	return;
}

int tin[2][MX];
int tout[2][MX];

vector<in> flt[2]; //flt[0] = ft[1] = {0};

void dfs(int u, int k)
{
	tin[k][u] = flt[k].size();
	if(cnt[k][u])
		flt[k].pb({lb[k][u], cnt[k][u]});
	for(int v: ch[k][u])
	{
		if(v == -1)
			continue;
		dfs(v, k);
	}
	tout[k][u] = flt[k].size();
	return;
}

in help(const string &s, int k)
{
	int u = 0;
	for(auto c: s)
	{
		if(ch[k][u][con[c]] == -1)
			return {1, 0};
		u = ch[k][u][con[c]];
	}
	return {tin[k][u], tout[k][u]-1};
}

struct ps_tree
{
	int tree[MX];
	int left[MX];
	int right[MX];
	int N;
	void build(int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
			return;
		left[id] = N++;
		right[id] = N++;
		build(left[id], l, m);
		build(right[id], m+1, r);
		return;
	}
	int init(int M)
	{
		N = 1;
		build(1, 0, M);
		return N++;
	}
	int copy(int u)
	{
		int x = N++;
		tree[x] = tree[u];
		left[x] = left[u];
		right[x] = right[u];
		return x;
	}
	int upd(int p, int val, int id, int l, int r)
	{
		int id_new = copy(id);
		if(l == r)
		{
			tree[id_new]+=val;
			return id_new;
		}
		int m = (l+r)/2;
		if(p <= m)
			left[id_new] = upd(p, val, left[id], l, m);
		else
			right[id_new] = upd(p, val, right[id], m+1, r);
		tree[id_new] = tree[left[id_new]] + tree[right[id_new]];
		return id_new;
	}
	int Query(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return 0;
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		int s1 = Query(ql, qr, left[id], l, m);
		int s2 = Query(ql, qr, right[id], m+1, r);
		return s1+s2;
	}
};

signed main()
{
	fast(); pre();
	//cout << "hey" << endl;
	int n, q; cin >> n >> q;
	string s;
	for(int i = 1; i <= n; i++)
	{
		cin >> s;
		add(s, 0, i);
		reverse(s.begin(), s.end());
		add(s, 1, i);
	}
	flt[0] = flt[1] = {{0,0}};
	dfs(0, 0); dfs(0, 1);

	//cout << "hey" << endl;
	int N = flt[0].size()-1;
	vector<int> pres(n+1);
	vector<int> VAL(N+1);
	for(int i = 1; i <= N; i++)
	{
		auto [lbl, cnt] = flt[0][i];
		pres[lbl] = i;
		VAL[i] = cnt;
	}
	
	//cout << "hey" << endl;

	vector<int> w(N+1);//where to change.
	for(int i = 1; i <= N; i++)
	{
		flt[1][i][0] = pres[flt[1][i][0]];
		w[flt[1][i][0]] = i;
	}

	//cout << "hi" << endl;

	ps_tree work;
	int root[N+1];
	root[0] = work.init(N);
	for(int i = 1; i <= N; i++)
		root[i] = work.upd(w[i], VAL[i], root[i-1], 0, N);

	//cout << "hey" << endl;
	array<in, 2> Q;
	for(int i = 0; i < q; i++)
	{
		string x, y; cin >> x >> y;
		reverse(y.begin(), y.end());
		Q = {help(x, 0), help(y, 1)};  
		if((Q[0][0] > Q[0][1]) || (Q[1][0] > Q[1][1]))
		{
			cout << "0\n";
			continue;
		}
		//cout << Q[0][0] << " " << Q[0][1] << " " << Q[1][0] << " " << Q[1][1] << endl;
		int ans = work.Query(Q[1][0], Q[1][1], root[Q[0][1]], 0, N) - work.Query(Q[1][0], Q[1][1], root[Q[0][0]-1], 0, N);
		cout << ans << "\n";
	}

	/*for(int i = 1; i <= N; i++)
		cout << VAL[i] << " ";
	cout << endl;
	for(int i = 1; i <= N; i++)
		cout << w[i] << " ";
	cout << endl;*/
	return 0;
}	

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