oj.uz

Submission #847024

# Submission time Handle Problem Language Result Execution time Memory
847024 2023-09-09T02:13:43 Z moremo9422 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1246 ms 196460 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 3 ms 11356 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 3 ms 11356 KB Output is correct
6 Correct 2 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 138 ms 122000 KB Output is correct
2 Correct 163 ms 123100 KB Output is correct
3 Correct 571 ms 123012 KB Output is correct
4 Correct 569 ms 122960 KB Output is correct
5 Correct 163 ms 157844 KB Output is correct
6 Correct 165 ms 158772 KB Output is correct
7 Correct 1246 ms 118020 KB Output is correct
8 Correct 185 ms 170216 KB Output is correct
9 Correct 254 ms 196460 KB Output is correct
10 Correct 1242 ms 87912 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 20248 KB Output is correct
2 Correct 163 ms 34680 KB Output is correct
3 Correct 214 ms 38628 KB Output is correct
4 Correct 247 ms 19048 KB Output is correct
5 Correct 131 ms 22732 KB Output is correct
6 Correct 170 ms 28496 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 3 ms 11356 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct
8 Correct 138 ms 122000 KB Output is correct
9 Correct 163 ms 123100 KB Output is correct
10 Correct 571 ms 123012 KB Output is correct
11 Correct 569 ms 122960 KB Output is correct
12 Correct 163 ms 157844 KB Output is correct
13 Correct 165 ms 158772 KB Output is correct
14 Correct 1246 ms 118020 KB Output is correct
15 Correct 185 ms 170216 KB Output is correct
16 Correct 254 ms 196460 KB Output is correct
17 Correct 1242 ms 87912 KB Output is correct
18 Correct 290 ms 20248 KB Output is correct
19 Correct 163 ms 34680 KB Output is correct
20 Correct 214 ms 38628 KB Output is correct
21 Correct 247 ms 19048 KB Output is correct
22 Correct 131 ms 22732 KB Output is correct
23 Correct 170 ms 28496 KB Output is correct
24 Correct 292 ms 135464 KB Output is correct
25 Correct 541 ms 183372 KB Output is correct
26 Correct 210 ms 118524 KB Output is correct
27 Correct 900 ms 125384 KB Output is correct
28 Correct 1025 ms 119600 KB Output is correct
29 Correct 1219 ms 71568 KB Output is correct