제출 #255374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255374		islingr	Examination (JOI19_examination)	C++14	0 / 100	228 ms	9712 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 eb(x...) emplace_back(x)
#define lb(x...) lower_bound(x)
#define all(x) begin(x), end(x)

using ll = int64_t;

const int N = 1 << 17;

int n, m;
int t[4 * N];
int query(int l, int r) {
	int sum = 0;
	for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
		if (l & 1) sum += t[l++];
		if (r & 1) sum += t[--r];
	}
	return sum;
}
void update(int p, int x) {
	for (t[p += m] += x; p >>= 1; ) t[p] = t[p << 1] + t[p << 1|1];
}

struct point {
	int x, y, z, idx;
	bool operator<(const point &p) {
		return tuple<int, int, int, int>(-x, y, z, -idx) < tuple<int, int, int, int>(-p.x, p.y, p.z, -p.idx);
	}
} a[2 * N], tmp[2 * N];
vector<int> cmp;
int ans[N];

void cdq(int l, int r) {
	if (r - l == 1) return;
	int m = (l + r) / 2;
	cdq(l, m); cdq(m, r);
	vector<int> op;
	int i = l, j = m, k = l;
	int cnt = 0;
	while (i < m && j < r) {
		if (a[j].y <= a[i].y) {
			if (!a[i].idx) ++cnt, update(a[i].z, 1), op.eb(a[i].z);
			tmp[k] = a[i++];
		} else {
			if (a[j].idx) ans[a[j].idx] += cnt - query(0, a[j].z);
			tmp[k] = a[j++];
		}
		++k;
	}
	while (i < m) tmp[k++] = a[i++];
	while (j < r) {
		if (a[j].idx) ans[a[j].idx] += cnt - query(0, a[j].z);
		tmp[k++] = a[j++];
	}
	rep(i, l, r) a[i] = tmp[i];
	for (int p : op) update(p, -1);
}

signed 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};
		cmp.eb(x + y);
	}
	rep(i, 0, q) {
		int x, y, z; cin >> x >> y >> z;
		a[i + n] = {x, y, z, i + 1};
		cmp.eb(z);
	}
	sort(all(cmp)); cmp.resize(m = unique(all(cmp)) - begin(cmp));
	rep(i, 0, n + q) a[i].z = lb(all(cmp), a[i].z) - begin(cmp);
	sort(a, a + n + q); cdq(0, n + q);
	rep(i, 0, q) cout << ans[i + 1] << '\n';
}

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