Submission #68457766

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define _f(i, l, r) for (int i = l; i <= r; ++i)
#define _r(i, r, l) for (int i = r; i >= l; --i)
#define FASTIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
const int N = 1e5+5, M = 1005, inf = 0xc0c0c0c0c0c0c0c0;
int n;
struct item {
    int t, x, y, a, q, id;
    inline friend bool operator < (const item& a, const item& b) {
        return a.t-a.x-a.y < b.t-b.x-b.y;
    }
    inline friend bool operator <= (const item& a, const item& b) {
        return a.t-a.x-a.y <= b.t-b.x-b.y;
    }
} a[N], b[N];
int p[N], t;
int f[N];
struct SegmentTree {
    int c[N];
    int st[N*20], tp;
    SegmentTree() { memset(c, 0xc0, sizeof(c)); }
    inline void clear() { for (; tp > 0; tp--) c[st[tp]] = inf; }
    inline void upd(int x, int v) {
        for (; x <= t; x += x & -x) st[++tp] = x, c[x] = max(c[x], v); 
    }
    inline int qry(int x) {
        int mx = inf;
        for (; x; x -= x & -x) mx = max(mx, c[x]);
        return mx;
    }
} sgt;
void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l+r)>>1;
    cdq(l, mid);
    copy(a+mid+1, a+r+1, b+mid+1);
    stable_sort(b+mid+1, b+r+1);
    int lt = l, rt = mid+1;
    sgt.clear();
    while (lt <= mid || rt <= r) {
        if (rt > r || (lt <= mid && a[lt] <= b[rt])) sgt.upd(a[lt].q, f[a[lt].id]), lt++;
        else f[b[rt].id] = max(f[b[rt].id], sgt.qry(b[rt].q)+b[rt].a), rt++;
    }
    cdq(mid+1, r);
    merge(a+l, a+mid+1, a+mid+1, a+r+1, b+l);
    copy(b+l, b+r+1, a+l);
}
signed main() {
	FASTIO;
    cin >> n;
    _f(i, 1, n) cin >> a[i].t >> a[i].x >> a[i].y >> a[i].a;
    a[++n] = {0,0,0,0,0,0};
    _f(i, 1, n) a[i].id = i, p[++t] = a[i].y;
    stable_sort(p+1, p+t+1);
    t = unique(p+1, p+t+1)-p-1;
    _f(i, 1, n) a[i].q = lower_bound(p+1, p+t+1, a[i].y)-p;
    stable_sort(a+1, a+n+1, [](const item& a, const item& b) { return a.t+a.x-a.y == b.t+b.x-b.y ? a.t < b.t : a.t+a.x-a.y < b.t+b.x-b.y; });
    memset(f, 0xc0, sizeof(f));
    f[n] = 0;
    cdq(1, n);
    cout << *max_element(f+1, f+n+1) << '\n';
	return 0;
}

Submission Info

Judge Result