Submission #255649

#	Time	Username	Problem	Language	Result	Execution time	Memory
255649		islingr	Examination (JOI19_examination)	C++17	100 / 100	746 ms	14200 KiB

examination

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)

const int N = 1 << 17;

int n;
struct P { int x, y, z, i; bool first; } a[2 * N], tmp[2 * N];
int ans[N];

void cdq2(int l, int r) {
	if (r - l == 1) return;
	int m = (l + r) / 2;
	cdq2(l, m); cdq2(m, r);
	int i = l, j = m, k = l, cnt = 0;
	while (i < m && j < r) {
		if (a[j].z <= a[i].z) {
			if (!a[i].i && a[i].first) ++cnt;
			tmp[k++] = a[i++];
		} else {
			if (a[j].i && !a[j].first) ans[a[j].i] += cnt;
			tmp[k++] = a[j++];
		}
	}
	while (i < m) tmp[k++] = a[i++];
	while (j < r) {
		if (a[j].i && !a[j].first) ans[a[j].i] += cnt;
		tmp[k++] = a[j++];
	}
	rep(i, l, r) a[i] = tmp[i];
}

void cdq(int l, int r) {
	if (r - l == 1) return;
	int m = (l + r) / 2;
	cdq(l, m); cdq(m, r);
	rep(i, l, m) a[i].first = 1;
	rep(i, m, r) a[i].first = 0;
	sort(a + l, a + r, [](P &a, P &b) { return pair(-a.y, a.i) < pair(-b.y, b.i); });
	cdq2(l, r);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int q; cin >> n >> q;
	rep(i, 0, n) {
		int x, y; cin >> x >> y;
		a[i + q] = {x, y, x + y, 0};
	}
	rep(i, 0, q) {
		int x, y, z; cin >> x >> y >> z;
		a[i] = {x, y, z, i + 1};
	}
	sort(a, a + n + q, [](P &a, P &b) { return pair(-a.x, a.i) < pair(-b.x, b.i); });
	cdq(0, n + q);
	rep(i, 0, q) cout << ans[i + 1] << '\n';
}

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