Submission #1258815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258815		kamrad	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	220 ms	275748 KiB

selling_rna

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

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 64;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxA   = 5;
const int maxN   = 1e5 + 10;

int n, m;
int NewIdx[26];

string s[maxN];

struct Node {
	int l, r;
	vector <int> st;
	Node *child[maxA];
	
	Node() {
		child[0] = child[1] = child[2] = child[3] = child[4] = nullptr;
		l = r = 0;
	}

	void extend(int idx) {
		if(child[idx] == nullptr)
			child[idx] = new Node();
	}

	void add(int i, int idx) {
		st.pb(idx);
		if(l == 0)
			l = idx;
		r = idx;

		if(i >= sz(s[idx]))
			return;

		int x = NewIdx[s[idx][i]-'A'];
		extend(x);
		child[x]->add(i+1, idx);
	}

	pair <Node*, bool> get(string &t, int idx) {
		if(idx >= sz(t)) {
			return make_pair(this, true);
		}

		int x = NewIdx[t[idx]-'A'];
		if(child[x] == nullptr)
			return make_pair(this, false);
		return child[x]->get(t, idx+1);
	}
};

Node *r = new Node();
Node *rv = new Node();

int main() {
	IOS;
	
	NewIdx['A'-'A'] = 0;
	NewIdx['C'-'A'] = 1;
	NewIdx['G'-'A'] = 2;
	NewIdx['U'-'A'] = 3;

	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> s[i];
	sort(s, s+n+1);

	for(int i = 1; i <= n; i++) {
		r->add(0, i);
		reverse(all(s[i]));
		rv->add(0, i);
	}

	while(m--) {
		string p, q;
		cin >> p >> q;
		reverse(all(q));

		pair<Node*, bool> x = r->get(p, 0);
		pair<Node*, bool> y = rv->get(q, 0);

		if(!(x.S & y.S)) {
			cout << 0 << "\n";
			continue;
		}
		
		int L = lower_bound(all((y.F)->st), (x.F)->l) - (y.F)->st.begin();
		int R = upper_bound(all((y.F)->st), (x.F)->r) - (y.F)->st.begin();
		cout << R-L << "\n";
	}
}

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