Submission #245560

#	Time	Username	Problem	Language	Result	Execution time	Memory
245560		ruler	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	182 ms	74744 KiB

selling_rna

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 1e5 + 5, M = 2e6 + 5, SGM = 4;

int t, clk, CNT[M], C[M][SGM], ST[M], FN[M], Z[N], ANS[N];
string S[N], PRE[N], SUF[N];
vector<pii> Q[N], T;

int Add(string &s) {
	int now = 0;
	for (char c : s) {
		if (!C[now][c - 'A']) C[now][c - 'A'] = ++t;
		now = C[now][c - 'A'];
		CNT[now]++;
	}
	return now;
}
void Compress(string &s) {
	for (char &c : s) {
		if (c == 'G') c = 'B';
		if (c == 'U') c = 'D';
	}
}
void DFS(int v) {
	ST[v] = clk++;
	for (int i = 0; i < SGM; i++) if (C[v][i]) DFS(C[v][i]);
	FN[v] = clk;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> S[i]; Compress(S[i]);
		Z[i] = Add(S[i]);
	}
	DFS(0);
	for (int i = 0; i < n; i++) T.push_back(make_pair(ST[Z[i]], i));
	sort(all(T));
	for (int i = 0; i < q; i++) {
		cin >> PRE[i] >> SUF[i]; Compress(PRE[i]), Compress(SUF[i]);
		int now = 0;
		for (char c : PRE[i]) {
			now = C[now][c - 'A'];
			if (!now) break;
		}
		if (now == 0) continue;
		reverse(all(SUF[i]));
		int r = lower_bound(all(T), make_pair(ST[now], 0)) - T.begin();
		int l = lower_bound(all(T), make_pair(FN[now], 0)) - T.begin();
		Q[r].push_back(make_pair(-1, i));
		Q[l].push_back(make_pair(+1, i));
	}
	memset(C, 0, sizeof C), memset(CNT, 0, sizeof CNT), t = 0;
	for (int i = 0; i < n; i++) reverse(all(S[i]));
	for (int i = 0; i <= n; i++) {
		for (pii p : Q[i]) {
			int now = 0;
			for (char c : SUF[p.second]) {
				now = C[now][c - 'A'];
				if (!now) break;
			}
			if (now == 0) continue;
			ANS[p.second] += p.first * CNT[now];
		}
		if (i < n) Add(S[T[i].second]);
	}
	for (int i = 0; i < q; i++) cout << ANS[i] << endl;
	

	return 0;
}

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