Submission #1913358

---

Source Code Expand

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

struct RARM {
	using t1 = int;
	using t2 = int;
	static t1 id1() { return 0; }
	static t2 id2() { return 0; }
	static t1 op1(const t1& l, const t1& r) { return max(l, r); }
	static t1 op2(const t1& l, const t2& r) { return l + r; }
	static t2 op3(const t2& l, const t2& r) { return l + r; }
};

template <typename M>
class LazySegmentTree {
	using T1 = typename M::t1;
	using T2 = typename M::t2;
	const int n;
	vector<T1> data;
	vector<T2> lazy;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	void push(int node) {
		if (lazy[node] == M::id2()) return;
		if (node < n) {
			lazy[node * 2] = M::op3(lazy[node * 2], lazy[node]);
			lazy[node * 2 + 1] = M::op3(lazy[node * 2 + 1], lazy[node]);
		}
		data[node] = M::op2(data[node], lazy[node]);
		lazy[node] = M::id2();
	}
	void suc(int l, int r, int node, int lb, int ub, T2 val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			lazy[node] = M::op3(lazy[node], val);
			return;
		}
		push(node);
		int c = (lb + ub) / 2;
		suc(l, r, node * 2, lb, c, val);
		suc(l, r, node * 2 + 1, c, ub, val);
		data[node] = M::op1(M::op2(data[node * 2], lazy[node * 2]), M::op2(data[node * 2 + 1], lazy[node * 2 + 1]));
	}
	T1 sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return M::id1();
		if (l <= lb && ub <= r) return M::op2(data[node], lazy[node]);
		push(node);
		int c = (lb + ub) / 2;
		return M::op1(sub(l, r, node * 2, lb, c), sub(l, r, node * 2 + 1, c, ub));
	}
public:
	LazySegmentTree(int n_) : n(size(n_)), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {}
	LazySegmentTree(int n_, T1 v1, T2 v2) : n(size(n_)), data(n * 2, v1), lazy(n * 2, v2) {}
	LazySegmentTree(const vector<T1>& data_) : n(size(data_.size())), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {
		init(data_);
	}
	void init() {
		for (int i = n - 1; i >= 1; i--) data[i] = M::op1(data[i * 2], data[i * 2 + 1]);
	}
	void init(const vector<T1>& data_) {
		for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
		init();
	}
	void update(int l, int r, T2 val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T1 find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

void compress(vector<int>& v, vector<int>& vs) {
	vs = v;
	sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
	for (auto& val : v) {
		val = lower_bound(vs.begin(), vs.end(), val) - vs.begin();
	}
}

int main()
{
	int N;
	cin >> N;
	vector<int> x(N), y(N), L(N);
	vector<tuple<int, int, int>> xyL;
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> L[i];
		xyL.emplace_back(x[i], y[i], L[i]);
	}
	sort(xyL.begin(), xyL.end());
	for (int i = 0; i < N; i++) {
		x[i] = get<0>(xyL[i]);
		y[i] = get<1>(xyL[i]);
		L[i] = get<2>(xyL[i]);
	}
	vector<int> xs, ys, Ls;
	compress(x, xs), compress(y, ys), compress(L, Ls);
	vector<int> rL(N);
	for (int i = 0; i < N; i++) {
		rL[L[i]] = i;
	}
	int res = 0;
	for (int i = N - 1; i >= 0; i--) {
		LazySegmentTree<RARM> lst(N);
		int ni = rL[i];
		int st = lower_bound(xs.begin(), xs.end(), xs[x[ni]] - Ls[i]) - xs.begin();
		int en = upper_bound(xs.begin(), xs.end(), xs[x[ni]] + Ls[i]) - xs.begin();
		for (int l = st, r = st; r < en; r++) {
			if (L[r] >= i) {
				int id = upper_bound(ys.begin(), ys.end(), ys[y[r]] + Ls[i]) - ys.begin() - 1;
				lst.update(y[r], id, 1);
			}
			while (xs[x[r]] - xs[x[l]] > Ls[i]) {
				if (L[l] >= i) {
					int id = upper_bound(ys.begin(), ys.end(), ys[y[l]] + Ls[i]) - ys.begin() - 1;
					lst.update(y[l], id, -1);
				}
				l++;
			}
			res = max(res, lst.find(0, N - 1));
		}
	}
	cout << res << endl;
	return 0;
}

Submission Info

Judge Result