Submission #492695

#	Time	Username	Problem	Language	Result	Execution time	Memory
492695		zhougz	Examination (JOI19_examination)	C++17	100 / 100	157 ms	10800 KiB

examination

/**
 *    author: zhougz
 *    created: 08/12/2021 19:18:23
**/
#include <bits/stdc++.h>

using namespace std;

int n, q;
const int MAXN = 100'050, MAXQ = 100'050;

struct ele {
	int x, y, z, idx;
};

vector<ele> arr;

int idx[MAXN + MAXQ], fw[MAXN + MAXQ], res[MAXQ];

int lsb(int x) {
	return x & -x;
}

void update(int x) {
	for (x++; x <= n + q; x += lsb(x)) {
		fw[x]++;
	}
}

int query(int x) {
	int ret = 0;
	for (x++; x != 0; x -= lsb(x)) {
		ret += fw[x];
	}
	return ret;
}

int query(int l, int r) {
	return query(r) - query(l - 1);
}

// The double sweep-line method.
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	arr.resize(n + q);
	for (int i = 0; i < n; i++) {
		cin >> arr[i].x >> arr[i].y;
		arr[i].z = arr[i].x + arr[i].y;
		arr[i].idx = i;
	}
	for (int i = n; i < n + q; i++) {
		cin >> arr[i].x >> arr[i].y >> arr[i].z;
		arr[i].z = max(arr[i].z, arr[i].x + arr[i].y);
		arr[i].idx = i;
	}
	auto by_z = [](const ele &l, const ele &r) {
		return l.z < r.z;
	};
	sort(arr.begin(), arr.end(), by_z);
	for (int i = 0; i < n + q; i++) {
		idx[arr[i].idx] = lower_bound(arr.begin(), arr.end(), arr[i], by_z) - arr.begin();
	}
	sort(arr.begin(), arr.end(), [](const ele &l, const ele &r) {
		if (l.y != r.y) {
			return l.y > r.y;
		}
		if (l.z != r.z) {
			return l.z > r.z;
		}
		return l.idx < r.idx; // Students first for this sweep
	});
	for (const auto &[x, y, z, id] : arr) {
		if (id < n) { // Student
			update(idx[id]);
		} else { // Query
			res[id - n] += query(idx[id], n + q - 1);
		}
	}
	fill(fw, fw + MAXN + MAXQ, 0);
	sort(arr.begin(), arr.end(), [](const ele &l, const ele &r) {
		if (l.x != r.x) {
			return l.x < r.x;
		}
		if (l.z != r.z) {
			return l.z < r.z;
		}
		return l.idx > r.idx; // Prevent removing too much (same x-coordinate)
	});
	for (const auto &[x, y, z, id] : arr) {
		if (id < n) {
			update(idx[id]);
		} else {
			res[id - n] -= query(idx[id], n + q - 1);
		}
	}
	for (int i = 0; i < q; i++) {
		cout << res[i] << '\n';
	}
	return 0;
}

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