Submission #102242

#	Time	Username	Problem	Language	Result	Execution time	Memory
102242		jasony123123	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	477 ms	329912 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***************************************/
const int MAXTRIE = 4000009;
const int MAXNM = 100009;
const int L = 200009; 
int N, M, ans[MAXNM];

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[MAXTRIE];
	int tsz = 1;

	int dfstim = 0;
	int P[MAXNM]; // for -(1-N)
	int L[MAXNM], R[MAXNM]; // 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;

struct events {
	int x, y, fl;
	events(int _x, int _y, int _fl) : x(_x), y(_y), fl(_fl) {}
};

int bit[L + 1];
void upd(int k, int val) {
	for (k++; k <= L; k += (k&-k))
		bit[k] += val;
}
int query(int k) {
	int temp = 0;
	for (k++; k > 0; k -= (k&-k))
		temp += bit[k];
	return temp;
}

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";
	//}

	v<events> alle;
	alle.reserve(N + 4 * M);
	FORE(i, 1, N)
		alle.push_back(events(tfor.P[i], trev.P[i], INT_MIN));
	FORE(i, 1, M) {
		alle.push_back(events(tfor.R[i], trev.R[i], +i));
		alle.push_back(events(tfor.L[i] - 1, trev.R[i], -i));
		alle.push_back(events(tfor.R[i], trev.L[i] - 1, -i));
		alle.push_back(events(tfor.L[i] - 1, trev.L[i] - 1, +i));
	}
	sort(all(alle), [](events &a, events &b) {
		return mp(a.x, a.fl) < mp(b.x, b.fl);
	});

	for (auto e : alle) {
		if (e.fl == INT_MIN)
			upd(e.y, 1);
		else if (e.fl < 0)
			ans[abs(e.fl)] -= query(e.y);
		else
			ans[e.fl] += query(e.y);
	}

	FORE(i, 1, M)
		cout << ans[i] << "\n";
}

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