제출 #245556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245556		ruler	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	295 ms	287380 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[N], C[M][SGM], W[M], ST[N], FN[N], ANS[N];
string S[N], PRE[N], SUF[N];
vector<pii> Q[M];
vector<int> Z[M];

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++, W[ST[v]] = v;
	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]);
		int node = Add(S[i]);
		Z[node].push_back(i);
	}
	DFS(0);
	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]));
		Q[ST[now]].push_back(make_pair(-1, i));
		Q[FN[now]].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 <= clk; 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];
		}
		for (int j : Z[W[i]]) Add(S[j]);
	}
	for (int i = 0; i < q; i++) cout << ANS[i] << endl;
	

	return 0;
}

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