Submission #1279005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279005		IBory	Examination (JOI19_examination)	C++20	100 / 100	243 ms	7928 KiB

examination

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007;
int X[MAX], Y[MAX], A[MAX], B[MAX], C[MAX], ans[MAX];
vector<pii> ord;

struct BIT {
	int T[MAX];
	void Update(int i, int v) {
		for (; i < MAX; i += i & -i) T[i] += v;
	}
	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;

void Solve(int L, int R) {
	int mid = (L + R) >> 1;

	vector<pii> P;
	for (int i = L; i <= mid; ++i) {
		auto [_, p] = ord[i];
		if (p > 0) P.emplace_back(X[p], p);
	}
	for (int i = mid + 1; i <= R; ++i) {
		auto [_, p] = ord[i];
		if (p < 0) P.emplace_back(A[-p], p);
	}

	sort(P.begin(), P.end(), greater<pii>());
	for (auto [_, n] : P) {
		if (n > 0) T.Update(Y[n], 1);
		else ans[-n] += T.Query(B[-n], MAX - 1); 
	}

	for (auto [_, n] : P) if (n > 0) T.Update(Y[n], -1);
	if (L != mid) Solve(L, mid);
	if (mid + 1 != R) Solve(mid + 1, R);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	vector<int> U;
	for (int i = 1; i <= N; ++i) {
		cin >> X[i] >> Y[i];
		U.push_back(Y[i]);
		ord.emplace_back(X[i] + Y[i], i);
	}

	U.push_back(-1);
	sort(U.begin(), U.end());
	U.erase(unique(U.begin(), U.end()), U.end());
	for (int i = 1; i <= N; ++i) Y[i] = lower_bound(U.begin(), U.end(), Y[i]) - U.begin();

	for (int i = 1; i <= Q; ++i) {
		cin >> A[i] >> B[i] >> C[i];
		B[i] = lower_bound(U.begin(), U.end(), B[i]) - U.begin();
		ord.emplace_back(C[i], -i);
	}

	sort(ord.begin(), ord.end(), greater<pii>());
	Solve(0, ord.size() - 1);

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

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57