Submission #965666

#	Time	Username	Problem	Language	Result	Execution time	Memory
965666		IBory	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	150 ms	29284 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40