Submission #255677

#	Time	Username	Problem	Language	Result	Execution time	Memory
255677		islingr	Examination (JOI19_examination)	C++17	100 / 100	561 ms	14172 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

const int N = 1 << 17;
int n, ans[N];
struct P { int x, y, z, i; bool first; } a[2 * N], b[2 * N], c[2 * 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 (b[j].z <= b[i].z) {
			if (!b[i].i && b[i].first) ++cnt;
			c[k++] = b[i++];
		} else {
			if (b[j].i && !b[j].first) ans[b[j].i] += cnt;
			c[k++] = b[j++];
		}
	}
	while (i < m) c[k++] = b[i++];
	while (j < r) {
		if (b[j].i && !b[j].first) ans[b[j].i] += cnt;
		c[k++] = b[j++];
	}
	rep(i, l, r) b[i] = c[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, r) a[i].first = i < m;
	merge(a + l, a + m, a + m, a + r, b + l, [](P &a, P &b) { return pair(-a.y, a.i) < pair(-b.y, b.i); });
	rep(i, l, r) a[i] = 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] = {x, y, x + y, 0};
	}
	rep(i, 0, q) {
		int x, y, z; cin >> x >> y >> z;
		a[i + n] = {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