AtCoder Beginner Contest 266 Ex Snuke Panic (2D)

/*

p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy

*/

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, f[maxn], lsh[maxn], tot;
struct node {
	ll t, x, y, v, z, id, k;
} a[maxn], b[maxn];

bool cmp1(node a, node b) {
	if (a.y != b.y) {
		return a.y < b.y;
	} else if (a.k != b.k) {
		return a.k < b.k;
	} else {
		return a.z < b.z;
	}
}

bool cmp2(node a, node b) {
	if (a.k != b.k) {
		return a.k < b.k;
	} else if (a.z != b.z) {
		return a.z < b.z;
	} else {
		return a.y < b.y;
	}
}

namespace BIT {
	ll c[maxn];
	
	void init() {
		for (int i = 0; i < maxn; ++i) {
			c[i] = -inf;
		}
	}
	
	void update(int x, ll d) {
		for (int i = x; i < maxn; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	ll query(int x) {
		ll res = -inf;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
	
	void clear(int x) {
		for (int i = x; i < maxn; i += (i & (-i))) {
			c[i] = -inf;
		}
	}
}

void cdq(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) >> 1;
	cdq(l, mid);
	for (int i = l; i <= r; ++i) {
		b[i] = a[i];
	}
	sort(b + l, b + mid + 1, cmp2);
	sort(b + mid + 1, b + r + 1, cmp2);
	int p1 = l, p2 = mid + 1;
	while (p1 <= mid && p2 <= r) {
		if (b[p1].k <= b[p2].k) {
			BIT::update(b[p1].z, f[b[p1].id]);
			++p1;
		} else {
			f[b[p2].id] = max(f[b[p2].id], BIT::query(b[p2].z) + b[p2].v);
			++p2;
		}
	}
	while (p1 <= mid) {
		BIT::update(b[p1].z, f[b[p1].id]);
		++p1;
	}
	while (p2 <= r) {
		f[b[p2].id] = max(f[b[p2].id], BIT::query(b[p2].z) + b[p2].v);
		++p2;
	}
	for (int i = l; i <= mid; ++i) {
		BIT::clear(b[i].z);
	}
	cdq(mid + 1, r);
}

void solve() {
	BIT::init();
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld%lld%lld", &a[i].t, &a[i].x, &a[i].y, &a[i].v);
		lsh[++tot] = a[i].t + a[i].x - a[i].y;
		a[i].k = a[i].t - a[i].x - a[i].y;
		a[i].id = i;
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		a[i].z = lower_bound(lsh + 1, lsh + tot + 1, a[i].t + a[i].x - a[i].y) - lsh + 1;
	}
	a[0].z = 1;
	sort(a + 1, a + n + 1, cmp1);
	f[0] = 0;
	for (int i = 1; i <= n; ++i) {
		f[i] = -inf;
	}
	cdq(0, n);
	printf("%lld\n", *max_element(f, f + n + 1));
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}