oj.uz

Submission #112368

# Submission time Handle Problem Language Result Execution time Memory
112368 2019-05-19T06:33:24 Z MAMBA Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 613 ms 348156 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 282232 KB Output is correct
2 Correct 244 ms 282204 KB Output is correct
3 Correct 234 ms 282360 KB Output is correct
4 Correct 231 ms 282232 KB Output is correct
5 Correct 230 ms 282232 KB Output is correct
6 Correct 228 ms 282224 KB Output is correct
7 Correct 233 ms 282232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 325688 KB Output is correct
2 Correct 534 ms 323416 KB Output is correct
3 Correct 426 ms 345840 KB Output is correct
4 Correct 418 ms 344128 KB Output is correct
5 Correct 584 ms 347388 KB Output is correct
6 Correct 613 ms 348156 KB Output is correct
7 Correct 314 ms 288376 KB Output is correct
8 Correct 425 ms 325240 KB Output is correct
9 Correct 424 ms 319096 KB Output is correct
10 Correct 376 ms 315740 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 283708 KB Output is correct
2 Correct 248 ms 283256 KB Output is correct
3 Correct 247 ms 283384 KB Output is correct
4 Correct 240 ms 283100 KB Output is correct
5 Correct 246 ms 283360 KB Output is correct
6 Correct 250 ms 283508 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 282232 KB Output is correct
2 Correct 244 ms 282204 KB Output is correct
3 Correct 234 ms 282360 KB Output is correct
4 Correct 231 ms 282232 KB Output is correct
5 Correct 230 ms 282232 KB Output is correct
6 Correct 228 ms 282224 KB Output is correct
7 Correct 233 ms 282232 KB Output is correct
8 Correct 582 ms 325688 KB Output is correct
9 Correct 534 ms 323416 KB Output is correct
10 Correct 426 ms 345840 KB Output is correct
11 Correct 418 ms 344128 KB Output is correct
12 Correct 584 ms 347388 KB Output is correct
13 Correct 613 ms 348156 KB Output is correct
14 Correct 314 ms 288376 KB Output is correct
15 Correct 425 ms 325240 KB Output is correct
16 Correct 424 ms 319096 KB Output is correct
17 Correct 376 ms 315740 KB Output is correct
18 Correct 244 ms 283708 KB Output is correct
19 Correct 248 ms 283256 KB Output is correct
20 Correct 247 ms 283384 KB Output is correct
21 Correct 240 ms 283100 KB Output is correct
22 Correct 246 ms 283360 KB Output is correct
23 Correct 250 ms 283508 KB Output is correct
24 Correct 521 ms 319008 KB Output is correct
25 Correct 512 ms 319968 KB Output is correct
26 Correct 495 ms 318328 KB Output is correct
27 Correct 399 ms 337016 KB Output is correct
28 Correct 414 ms 295160 KB Output is correct
29 Correct 307 ms 285176 KB Output is correct