제출 #255677

#제출 시각아이디문제언어결과실행 시간메모리
255677islingrExamination (JOI19_examination)C++17
100 / 100
561 ms14172 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...