Submission #112368

#	Time	Username	Problem	Language	Result	Execution time	Memory
112368		MAMBA	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	613 ms	348156 KiB

selling_rna

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 2e6 + 10;

constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

map<char , int> mp({{'A' , 0} , {'G' , 1} , {'C' , 2} , {'U' , 3}});

int n , m, cnt[2];
string s[N], h[N], q[N];
int nxt[2][N][4];
vector<pii> vec[N];

int st[N], en[N], tme;
void dfs1(int v) {
	st[v] = tme++;
	rep(i , 0 , 4)
		if (nxt[0][v][i])
			dfs1(nxt[0][v][i]);
	en[v] = tme;
}

int sz[N], pos[N], res[N];
vi have[N];

int seg[N << 1];

inline void segClear(int v = 1) {
	if (!seg[v]) return;
	seg[v] = 0;
	if ((v << 1) < (N << 1)) segClear(v << 1);
	if ((v << 1 | 1) < (N << 1)) segClear(v << 1 | 1);
}

inline void segAdd(int pos) {
	for (pos += cnt[0] + 1; pos; pos >>= 1)
		seg[pos]++;
}

inline int segGet(int l , int r) {	int res = 0;
	for (l += cnt[0] + 1, r += cnt[0] + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res += seg[l++];
		if (r & 1) res += seg[--r];
	}
	return res;
}

void dfsAdd(int v) {
	for (auto e : have[v])
		segAdd(st[pos[e]]);
	rep(i , 0  ,4) {
		int u = nxt[1][v][i];
		if (u)
			dfsAdd(u);

	}
}

void dfs2(int v) {
	int mx = -1, id =-1;
	rep(i , 0 , 4) 
		if (nxt[1][v][i] && smax(mx , sz[nxt[1][v][i]]))
			id = i;
	rep(i , 0 , 4) {
		int u = nxt[1][v][i];
		if (u && i != id) {
			dfs2(u);
			segClear();		
		}
	}
	if (~id) 
		dfs2(nxt[1][v][id]);
	rep(i , 0 , 4) {
		int u = nxt[1][v][i];
		if (u && i != id) 
			dfsAdd(u);
	}
	for (auto e : have[v])
		segAdd(st[pos[e]]);

	for (auto e : vec[v])
		res[e.second] = segGet(st[e.first] , en[e.first]);
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

#ifndef LOCAL
	//	fileIO("forbidden1");
#endif

	cin >> n >> m;
	rep(i  , 0 , n) {
		cin >> s[i];

		auto f = [i](int id) -> int {
			int now = 0;	
			if (id == 1) sz[0]++;
			for (auto e : s[i]) {
				if (!nxt[id][now][mp[e]])
					nxt[id][now][mp[e]] = ++cnt[id];
				now = nxt[id][now][mp[e]];	
				if (id == 1) sz[now]++;
			}
			return now;
		};

		pos[i] = f(0);
		reverse(all(s[i]));
		have[f(1)].pb(i);
	}

	rep(i , 0 , m) {
		cin >> h[i] >> q[i];
		reverse(all(q[i]));

		auto f = [](int id, string &st) -> int {
			int now = 0;
			for (auto e : st) {
				if (!nxt[id][now][mp[e]]) return -1;
				now = nxt[id][now][mp[e]];
			}
			return now;
		};

		int lid = f(0, h[i]);
		int rid = f(1 ,q[i]);

		if (!~min(lid , rid))
			continue;
		vec[rid].pb({lid , i});
	}

	dfs1(0);
	dfs2(0);

	rep(i , 0 , m)
		cout << res[i] << '\n';


	return 0;
}

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