oj.uz

Submission #848308

# Submission time Handle Problem Language Result Execution time Memory
848308 2023-09-12T04:52:10 Z qthang2k11 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1272 ms 193244 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define next defined_next

const int mod = 1e9 + 696969, base = 311;

const int N = 1e5 + 5, S = sqrt(N);
vector<int> hs[N];
string s[N];
int n, q;

struct Node {
	int cnt;
	Node *nxt[4];
	
	Node() {
		cnt = 0;
		for (int i = 0; i < 4; i++)
			nxt[i] = nullptr;
	}
	
	Node *next(int x) {
		if (nxt[x] == nullptr)
			nxt[x] = new Node();
		return nxt[x];
	}
};

struct Trie {
	Node *root = new Node();
	
	Trie() = default;
	
	void insert(string s) {
		reverse(s.begin(), s.end());
		Node *cur = root;
		for (char ch: s) {
			cur = cur->next(ch);
			cur->cnt++;
		}
	}
	
	int get(string s) {
		reverse(s.begin(), s.end());
		Node *cur = root;
		for (char ch: s) {
			if (cur->nxt[(int)ch] == nullptr)
				return 0;
			cur = cur->nxt[(int)ch];
		}
		return cur->cnt;
	}
} blocks[N / S + 5];

map<char, int> mp;
void compress(string &s) {
	for (char &ch: s)
		ch = mp[ch];
}

void print_debug(string s, bool el = true) {
	map<char, char> rev;
	rev[0] = 'A';
	rev[1] = 'C';
	rev[2] = 'G';
	rev[3] = 'U';
	for (char c: s)
		cerr << rev[c];
	if (el) cerr << '\n';
}

struct pr {
	string s;
	vector<int> hs;
	
	pr() = default;
	pr(const string &str) {
		s = str;
		int n = s.size();
		hs.resize(n + 1);
		hs[0] = 1;
		for (int i = 1; i <= n; i++)
			hs[i] = (1LL * hs[i - 1] * base % mod + s[i - 1] + 1) % mod;
	}
	
	bool operator < (const pr &other) const {
		int len_x = s.size(), len_y = other.s.size();
		int l = 1, r = min(len_x, len_y), last_equal = 0;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (hs[mid] == other.hs[mid]) {
				last_equal = mid;
				l = mid + 1;
			} else r = mid - 1;
		}
		if (last_equal == len_x && last_equal == len_y)
			return false;
		if (last_equal == len_x || s[last_equal] < other.s[last_equal])
			return true;
		return false;
	}
	
} to_sort[N];

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("rna.inp", "r"))
		freopen("rna.inp", "r", stdin),
		freopen("rna.out", "w", stdout);
	mp['A'] = 0;
	mp['C'] = 1;
	mp['G'] = 2;
	mp['U'] = 3;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		compress(s[i]);
		to_sort[i] = pr(s[i]);
	}
	sort(to_sort, to_sort + n);
	for (int i = 0; i < n; i++)
		s[i] = to_sort[i].s;
	// cerr << "SORTED:\n";
	// for (int i = 0; i < n; i++)
		// print_debug(s[i]);
	for (int i = 0; i < n; i++) 
		blocks[i / S].insert(s[i]);
	while (q--) {
		string pre, suf;
		cin >> pre >> suf;
		compress(pre);
		compress(suf);
		int pre_len = pre.size(), suf_len = suf.size();
		int l = [&] () -> int {
			int l = 0, r = n - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (s[mid] >= pre) {
					ans = mid;
					r = mid - 1;
				} else l = mid + 1;
			}
			if (ans != -1 && (int)s[ans].size() >= pre_len && s[ans].substr(0, pre_len) == pre)
				return ans;
			return -1;
		}();
		int r = [&] (int l) -> int {
			int r = n - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if ((int)s[mid].size() >= pre_len && s[mid].substr(0, pre_len) == pre) {
					ans = mid;
					l = mid + 1;
				} else r = mid - 1;
			}
			if (ans != -1 && (int)s[ans].size() >= pre_len && s[ans].substr(0, pre_len) == pre)
				return ans;
			return -1;
		}(l);
		if (l != -1 && r != -1 && l <= r) {
			cout << ([&] () -> int {
				int res = 0;
				Trie ans;
				int blockl = l / S, blockr = r / S;
				if (blockl == blockr) {
					for (int i = l; i <= r; i++) 
						if ((int)s[i].size() >= suf_len)
							ans.insert(s[i].substr((int)s[i].size() - suf_len));
					res = ans.get(suf);
				} else {
					for (int i = (blockl + 1) * S - 1; i >= l; i--)
						if ((int)s[i].size() >= suf_len)
							ans.insert(s[i].substr((int)s[i].size() - suf_len));
					for (int i = blockr * S; i <= r; i++)
						if ((int)s[i].size() >= suf_len)
							ans.insert(s[i].substr((int)s[i].size() - suf_len));
					res = ans.get(suf);
					for (int i = blockl + 1; i < blockr; i++)
						res += blocks[i].get(suf);
				}
				return res;
			}());
		} else cout << 0;
		cout << '\n';
	}
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:111:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen("rna.inp", "r", stdin),
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen("rna.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 3 ms 11356 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 120516 KB Output is correct
2 Correct 157 ms 120840 KB Output is correct
3 Correct 568 ms 120820 KB Output is correct
4 Correct 548 ms 120568 KB Output is correct
5 Correct 157 ms 156692 KB Output is correct
6 Correct 157 ms 157296 KB Output is correct
7 Correct 1241 ms 114880 KB Output is correct
8 Correct 174 ms 167188 KB Output is correct
9 Correct 238 ms 193244 KB Output is correct
10 Correct 1238 ms 86136 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 20184 KB Output is correct
2 Correct 150 ms 34900 KB Output is correct
3 Correct 214 ms 38164 KB Output is correct
4 Correct 247 ms 18828 KB Output is correct
5 Correct 131 ms 22616 KB Output is correct
6 Correct 167 ms 27896 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 3 ms 11356 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct
8 Correct 131 ms 120516 KB Output is correct
9 Correct 157 ms 120840 KB Output is correct
10 Correct 568 ms 120820 KB Output is correct
11 Correct 548 ms 120568 KB Output is correct
12 Correct 157 ms 156692 KB Output is correct
13 Correct 157 ms 157296 KB Output is correct
14 Correct 1241 ms 114880 KB Output is correct
15 Correct 174 ms 167188 KB Output is correct
16 Correct 238 ms 193244 KB Output is correct
17 Correct 1238 ms 86136 KB Output is correct
18 Correct 284 ms 20184 KB Output is correct
19 Correct 150 ms 34900 KB Output is correct
20 Correct 214 ms 38164 KB Output is correct
21 Correct 247 ms 18828 KB Output is correct
22 Correct 131 ms 22616 KB Output is correct
23 Correct 167 ms 27896 KB Output is correct
24 Correct 276 ms 133204 KB Output is correct
25 Correct 529 ms 181264 KB Output is correct
26 Correct 192 ms 116052 KB Output is correct
27 Correct 889 ms 123188 KB Output is correct
28 Correct 983 ms 116932 KB Output is correct
29 Correct 1272 ms 69816 KB Output is correct