Submission #60706935

---

Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1012345678;

class sparse_table {
private:
	vector<vector<int> > v;
public:
	sparse_table() : v() {}
	sparse_table(const vector<int>& a) {
		int n = a.size();
		int bits = (n >= 3 ? 32 - __builtin_clz(n - 1) : 1);
		v = vector<vector<int> >(bits);
		v[0] = a;
		for (int i = 1; i < bits; i++) {
			v[i].resize(n - (1 << i) + 1);
			for (int j = 0; j <= n - (1 << i); j++) {
				v[i][j] = max(v[i - 1][j], v[i - 1][j + (1 << (i - 1))]);
			}
		}
	}
	int range_max(int l, int r) const {
		if (l >= r) {
			return -INF;
		}
		int b = (r - l >= 3 ? 31 - __builtin_clz(r - l - 1) : 0);
		return max(v[b][l], v[b][r - (1 << b)]);
	}
};

class segment_tree {
private:
	int size;
	vector<int> val;
	vector<int> lazy;
	void push(int k) {
		if (lazy[k] != 0) {
			val[k] += lazy[k];
			if (k < size) {
				lazy[k * 2 + 0] += lazy[k];
				lazy[k * 2 + 1] += lazy[k];
			}
			lazy[k] = 0;
		}
	}
public:
	segment_tree() : size(0), val(), lazy() {}
	segment_tree(int n) : size(1 << (n >= 2 ? 32 - __builtin_clz(n - 1) : 0)) {
		val = vector<int>(size * 2, 0);
		lazy = vector<int>(size * 2, 0);
	}
	void range_add(int l, int r, int x) {
		auto recur = [&](auto& self, int k, int s, int t) -> void {
			if (l <= s && t <= r) {
				lazy[k] += x;
				push(k);
				return;
			}
			push(k);
			if (r <= s || t <= l) {
				return;
			}
			self(self, k * 2 + 0, s, (s + t) / 2);
			self(self, k * 2 + 1, (s + t) / 2, t);
			val[k] = max(val[k * 2 + 0], val[k * 2 + 1]);
		};
		recur(recur, 1, 0, size);
	}
	int range_max(int l, int r) {
		auto recur = [&](auto& self, int k, int s, int t) -> int {
			push(k);
			if (l <= s && t <= r) {
				return val[k];
			}
			if (r <= s || t <= l) {
				return -INF;
			}
			int lc = self(self, k * 2 + 0, s, (s + t) / 2);
			int rc = self(self, k * 2 + 1, (s + t) / 2, t);
			val[k] = max(val[k * 2 + 0], val[k * 2 + 1]);
			return max(lc, rc);
		};
		return recur(recur, 1, 0, size);
	}
};

int solve(int N, const vector<int>& X, const vector<int>& A) {
	vector<int> XA1(N), XA2(N);
	for (int i = 0; i < N; i++) {
		XA1[i] = A[i] + X[i];
		XA2[i] = A[i] - X[i];
	}
	sparse_table sp1(XA1), sp2(XA2);
	vector<int> L(N), R(N);
	for (int i = 0; i < N; i++) {
		int la = -1, ra = i;
		while (ra - la > 1) {
			int m = (la + ra) / 2;
			if (sp1.range_max(m, i) > X[i] + A[i]) {
				la = m;
			} else {
				ra = m;
			}
		}
		L[i] = ra;
		int pos = lower_bound(X.begin(), X.end(), X[i] + A[i]) - X.begin();
		if (sp1.range_max(i + 1, pos) >= X[i] + A[i]) {
			int lb = i, rb = pos;
			while (rb - lb > 1) {
				int m = (lb + rb) / 2;
				if (sp1.range_max(i + 1, m) >= X[i] + A[i]) {
					rb = m;
				} else {
					lb = m;
				}
			}
			R[i] = lb - 1;
		} else {
			int lc = pos, rc = N + 1;
			while (rc - lc > 1) {
				int m = (lc + rc) / 2;
				if (sp2.range_max(pos, m) >= -(X[i] + A[i])) {
					rc = m;
				} else {
					lc = m;
				}
			}
			R[i] = lc - 1;
		}
	}
	vector<vector<int> > dec(N);
	for (int i = 0; i < N; i++) {
		dec[R[i]].push_back(i);
	}
	int ans = 0;
	segment_tree seg(N);
	for (int i = 0; i < N; i++) {
		seg.range_add(L[i], i + 1, 1);
		int subans = seg.range_max(0, N);
		ans = max(ans, subans);
		for (int j : dec[i]) {
			seg.range_add(L[j], j + 1, -1);
		}
	}
	return ans;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int id = 1; id <= T; id++) {
		int N;
		cin >> N;
		vector<int> X(N), A(N);
		for (int i = 0; i < N; i++) {
			cin >> X[i] >> A[i];
		}
		int ans = solve(N, X, A);
		cout << ans << '\n';
	}
	return 0;
}

Submission Info

Judge Result