제출 #470451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470451		Namnamseo	Examination (JOI19_examination)	C++17	100 / 100	1502 ms	286172 KiB

examination

#include <algorithm>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using pp=pair<int,int>;
using vi=vector<int>;
const int maxn = int(1e5) + 10;
#define all(v) v.begin(), v.end()
#define pb push_back
#define x first
#define y second

int n;
pp d[maxn];

struct MergeSortTree {
	int m; vi xs, *t;

	void init(int l, int r) {
		xs.resize(r-l);
		for (m=1; m<r-l; m*=2);
		t = new vector<int>[m*2];
		for (int i=l; i<r; ++i) xs[i-l] = d[i].x;
		sort(all(xs));
		for (int i=l; i<r; ++i) {
			int x, y; tie(x, y) = d[i];
			x = lower_bound(all(xs), x) - xs.begin();
			t[x+m].pb(y);
		}
		for (int i=0; i<int(xs.size()); ++i) sort(all(t[m+i]));
		for (int i=m-1; 1<=i; --i) {
			auto &v=t[i], &vl=t[i*2], &vr=t[i*2+1];
			v.resize(vl.size()+vr.size());
			merge(all(vl), all(vr), v.begin());
		}
	}

	int rect(int l, int r, int d, int u) {
		l = lower_bound(all(xs), l) - xs.begin();
		r = upper_bound(all(xs), r) - xs.begin() - 1;
		if (l > r || d > u) return 0;
		int ret = 0;
		auto f = [&](vi &v) { ret += upper_bound(all(v), u) - lower_bound(all(v), d); };
		for (l+=m, r+=m; l<=r; l/=2, r/=2) {
			if (l%2 == 1) f(t[l++]);
			if (r%2 == 0) f(t[r--]);
		}
		return ret;
	}
} mst[262144];

void init(int p, int l, int r) {
	mst[p].init(l, r);
	if (l+1 == r) return;
	int md = (l+r)/2;
	init(p*2, l, md); init(p*2+1, md, r);
}

struct { int l, r, d, u; } Q;
int rect(int sl, int sr, int p, int l, int r) {
	if (sr<=l || r<=sl) return 0;
	if (sl<=l && r<=sr) return mst[p].rect(Q.l, Q.r, Q.d, Q.u);
	int md = (l+r)/2;
	return rect(sl, sr, p*2, l, md) + rect(sl, sr, p*2+1, md, r);
}

bool pcomp(const pp &a, const pp &b) {
	return (a.x+a.y) < (b.x+b.y);
}

int main() { cin.tie(0)->sync_with_stdio(0);
	int q; cin >> n >> q;
	for (int i=0; i<n; ++i) cin >> d[i].x >> d[i].y;
	sort(d, d+n, pcomp);
	init(1, 0, n);

	for(;q--;) {
		int x, y, s; cin >> x >> y >> s;
		int j = lower_bound(d, d+n, pp{s, 0}, pcomp)-d;
		const int inf = int(1e9) + 10;
		Q = {x, inf, y, inf};
		cout << rect(j, n, 1, 0, n) << '\n';
	}
	return 0;
}

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