oj.uz

Submission #681711

# Submission time Handle Problem Language Result Execution time Memory
681711 2023-01-13T21:20:04 Z NK_ Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 535 ms 426312 KB 
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int K = 4;
const int MX = 2e6 + 10;

struct node {
	vector<int> nxt, who;
	int sz;

	node() { nxt = vector<int>(K, -1); who = {}; sz = 0; }
};

template<int MX> struct Trie {
	int cur = 1;
	node T[MX];

	void add(const string &S, int IDX) {
		int v = 0;
		for(auto c : S) {
			if (T[v].nxt[c-'A'] == -1) {
				T[v].nxt[c-'A'] = cur++; 
			}
			T[v].sz++;
			T[v].who.push_back(IDX);

			v = T[v].nxt[c-'A'];
		}

		T[v].sz++;
		T[v].who.push_back(IDX);
	}

	array<int, 2> query(const string &S) {
		int v = 0;
		for(auto c : S) {
			if (T[v].nxt[c-'A'] == -1) return {-1, -1};
			v = T[v].nxt[c-'A'];
		}
		return {T[v].who.front(), T[v].who.back()};
	}

	int query(const string &S, int L, int R) {
		int v = 0; 
		for(auto c : S) {
			if (T[v].nxt[c-'A'] == -1) return 0;
			v = T[v].nxt[c-'A'];
		}
		return int(upper_bound(begin(T[v].who), end(T[v].who), R) - lower_bound(begin(T[v].who), end(T[v].who), L));
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	Trie<MX> pfx, sfx;

	auto alter = [&](string &S) {
		for(auto &c : S) {
			if (c == 'U') c = 'D';
			if (c == 'G') c = 'B';
		}
	};

	int N, Q; cin >> N >> Q;
	vector<string> A;
	for(int i = 0; i < N; i++) {
		string s; cin >> s; alter(s);
		A.push_back(s);
	}

	sort(begin(A), end(A));

	for(int i = 0; i < N; i++) {
		pfx.add(A[i], i);
		reverse(begin(A[i]), end(A[i]));
		sfx.add(A[i], i);
	}

	while(Q--) {
		string p, s; cin >> p >> s; alter(p); alter(s);
		reverse(begin(s), end(s));
		auto [L, R] = pfx.query(p);
		cout << sfx.query(s, L, R) << nl;
	}



    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 344660 KB Output is correct
2 Correct 248 ms 344644 KB Output is correct
3 Correct 249 ms 344664 KB Output is correct
4 Correct 242 ms 344632 KB Output is correct
5 Correct 240 ms 344696 KB Output is correct
6 Correct 243 ms 344796 KB Output is correct
7 Correct 253 ms 344712 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 423804 KB Output is correct
2 Correct 495 ms 419924 KB Output is correct
3 Correct 459 ms 422724 KB Output is correct
4 Correct 421 ms 419248 KB Output is correct
5 Correct 505 ms 425160 KB Output is correct
6 Correct 472 ms 426312 KB Output is correct
7 Correct 378 ms 368660 KB Output is correct
8 Correct 525 ms 409792 KB Output is correct
9 Correct 485 ms 401492 KB Output is correct
10 Correct 432 ms 398184 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 348804 KB Output is correct
2 Correct 318 ms 347472 KB Output is correct
3 Correct 321 ms 348160 KB Output is correct
4 Correct 302 ms 347896 KB Output is correct
5 Correct 304 ms 347456 KB Output is correct
6 Correct 312 ms 348020 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 344660 KB Output is correct
2 Correct 248 ms 344644 KB Output is correct
3 Correct 249 ms 344664 KB Output is correct
4 Correct 242 ms 344632 KB Output is correct
5 Correct 240 ms 344696 KB Output is correct
6 Correct 243 ms 344796 KB Output is correct
7 Correct 253 ms 344712 KB Output is correct
8 Correct 468 ms 423804 KB Output is correct
9 Correct 495 ms 419924 KB Output is correct
10 Correct 459 ms 422724 KB Output is correct
11 Correct 421 ms 419248 KB Output is correct
12 Correct 505 ms 425160 KB Output is correct
13 Correct 472 ms 426312 KB Output is correct
14 Correct 378 ms 368660 KB Output is correct
15 Correct 525 ms 409792 KB Output is correct
16 Correct 485 ms 401492 KB Output is correct
17 Correct 432 ms 398184 KB Output is correct
18 Correct 312 ms 348804 KB Output is correct
19 Correct 318 ms 347472 KB Output is correct
20 Correct 321 ms 348160 KB Output is correct
21 Correct 302 ms 347896 KB Output is correct
22 Correct 304 ms 347456 KB Output is correct
23 Correct 312 ms 348020 KB Output is correct
24 Correct 471 ms 411796 KB Output is correct
25 Correct 535 ms 412008 KB Output is correct
26 Correct 483 ms 411096 KB Output is correct
27 Correct 484 ms 411028 KB Output is correct
28 Correct 466 ms 379972 KB Output is correct
29 Correct 367 ms 362040 KB Output is correct