oj.uz

Submission #965666

# Submission time Handle Problem Language Result Execution time Memory
965666 2024-04-19T04:27:03 Z IBory Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 150 ms 29284 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007;
string S[MAX], RS[MAX];
int Y[MAX], ans[MAX];
pii RY[MAX];
vector<int> RX[MAX];

struct BIT {
	int T[MAX];
	void Update(int i) {
		for(; i < MAX; i += i & -i) T[i]++;
	}
	int Query(int L, int R) {
		int ret = 0; L--;
		for (; R; R -= R & -R) ret += T[R];
		for (; L; L -= L & -L) ret -= T[L];
		return ret;
	}
} T;

pii GetRange(int N, string* S, string P) {
	pii ret = {0, 0};
	ret.first = (lower_bound(S + 1, S + N + 1, P) - S) - 1;
	P.back()++;
	ret.second = (lower_bound(S + 1, S + N + 1, P) - S) - 1;
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	for (int i = 1; i <= N; ++i) cin >> S[i];
	sort(S + 1, S + N + 1);

	vector<pair<string, int>> P;
	P.emplace_back("A", 0);
	for (int i = 1; i <= N; ++i) {
		string r = S[i];
		reverse(r.begin(), r.end());
		P.emplace_back(r, i);
	}
	sort(P.begin(), P.end());
	for (int i = 1; i <= N; ++i) {
		Y[P[i].second] = i;
		RS[i] = P[i].first;
	}

	for (int i = 1; i <= Q; ++i) {
		string A, B;
		cin >> A >> B;
		reverse(B.begin(), B.end());

		pii x = GetRange(N, S, A);
		RY[i] = GetRange(N, RS, B); RY[i].first++;
		RX[x.second].push_back(i);
		RX[x.first].push_back(-i);
	}

	for (int i = 1; i <= N; ++i) {
		T.Update(Y[i]);
		for (int n : RX[i]) {
			auto [l, r] = RY[abs(n)];
			if (n < 0) ans[abs(n)] -= T.Query(l, r);
			else ans[abs(n)] += T.Query(l, r);
		}
	}

	for (int i = 1; i <= Q; ++i) cout << ans[i] << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21044 KB Output is correct
2 Correct 25 ms 21268 KB Output is correct
3 Correct 21 ms 21076 KB Output is correct
4 Correct 21 ms 21164 KB Output is correct
5 Correct 18 ms 17548 KB Output is correct
6 Correct 18 ms 17668 KB Output is correct
7 Correct 20 ms 21072 KB Output is correct
8 Correct 27 ms 23268 KB Output is correct
9 Correct 28 ms 23204 KB Output is correct
10 Correct 18 ms 20664 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14340 KB Output is correct
2 Correct 32 ms 13028 KB Output is correct
3 Correct 39 ms 14544 KB Output is correct
4 Correct 34 ms 15052 KB Output is correct
5 Correct 36 ms 12892 KB Output is correct
6 Correct 41 ms 13776 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 11008 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 16 ms 21044 KB Output is correct
9 Correct 25 ms 21268 KB Output is correct
10 Correct 21 ms 21076 KB Output is correct
11 Correct 21 ms 21164 KB Output is correct
12 Correct 18 ms 17548 KB Output is correct
13 Correct 18 ms 17668 KB Output is correct
14 Correct 20 ms 21072 KB Output is correct
15 Correct 27 ms 23268 KB Output is correct
16 Correct 28 ms 23204 KB Output is correct
17 Correct 18 ms 20664 KB Output is correct
18 Correct 47 ms 14340 KB Output is correct
19 Correct 32 ms 13028 KB Output is correct
20 Correct 39 ms 14544 KB Output is correct
21 Correct 34 ms 15052 KB Output is correct
22 Correct 36 ms 12892 KB Output is correct
23 Correct 41 ms 13776 KB Output is correct
24 Correct 36 ms 21952 KB Output is correct
25 Correct 57 ms 22376 KB Output is correct
26 Correct 30 ms 21608 KB Output is correct
27 Correct 47 ms 21864 KB Output is correct
28 Correct 150 ms 29284 KB Output is correct
29 Correct 122 ms 20152 KB Output is correct