Submission #102238

#	Time	Username	Problem	Language	Result	Execution time	Memory
102238		jasony123123	Selling RNA Strands (JOI16_selling_rna)	C++11	35 / 100	1587 ms	315860 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
#define mp make_pair
typedef long long ll;
typedef pair<int, int > pii;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/*************************JOI16_selling_rna***************************************/
int N, M;

int conv(char c) {
	if (c == 'A') return 0;
	if (c == 'C') return 1;
	if (c == 'U') return 2;
	return 3;
}

struct Node {
	int nxt[4];
	v<int> str;
	Node() { memset(nxt, -1, sizeof nxt); }
	v<int> getChildren() {
		v<int> chi;
		FOR(i, 0, 4) if (nxt[i] != -1) chi.push_back(nxt[i]);
		return chi;
	}
};

struct Trie {
	Node t[4000009];
	int tsz = 1;

	int dfstim = 0;
	int P[100001]; // for -(1-N)
	int L[100001], R[100001]; // for +(1-M)

	void addTrieNode(string &s, int num) {
		int cur = 0;
		for (char &cc : s) {
			int c = conv(cc);
			if (t[cur].nxt[c] == -1)
				t[cur].nxt[c] = tsz++;
			cur = t[cur].nxt[c];
		}
		t[cur].str.push_back(num);
	}

	void dfs(int cur) {
		if (t[cur].str.size()>0)
			dfstim++;
		for (int x : t[cur].str)
			if (x < 0) P[abs(x)] = dfstim;
			else L[x] = dfstim;

		v<int> adj = t[cur].getChildren();
		for (auto nex : adj)
			dfs(nex);

		if (t[cur].str.size()>0)
			dfstim++;
		for (int x : t[cur].str)
			if (x > 0) R[x] = dfstim;
	}
} tfor, trev;

int main() {
	io();
	cin >> N >> M;
	FORE(i, 1, N) {
		string s; cin >> s;
		tfor.addTrieNode(s, -i);
		reverse(all(s));
		trev.addTrieNode(s, -i);
	}
	FORE(i, 1, M) {
		string p, q; cin >> p >> q;
		tfor.addTrieNode(p, i);
		reverse(all(q));
		trev.addTrieNode(q, i);
	}
	tfor.dfs(0);
	trev.dfs(0);

	//FORE(i, 1, N) {
	//	printf("org str; point @ (%d, %d) \n", tfor.P[i], trev.P[i]);
	//}
	//FORE(i, 1, M) {
	//	printf("org query; rect @ x(%d, %d), y(%d, %d) \n", tfor.L[i], tfor.R[i], trev.L[i], trev.R[i]);
	//}
	FORE(i, 1, M) {
		int ans = 0;
		FORE(k, 1, N) if (tfor.L[i] <= tfor.P[k] && tfor.P[k] <= tfor.R[i] && trev.L[i] <= trev.P[k] && trev.P[k] <= trev.R[i])
			ans++;
		cout << ans << "\n";
	}
}

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