#include using namespace std; using int64 = long long; // const int mod = 1e9 + 7; const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in: v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e: t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } #line 1 "structure/wavelet/succinct-indexable-dictionary.cpp" /** * @brief Succinct Indexable Dictionary(完備辞書) */ struct SuccinctIndexableDictionary { size_t length; size_t blocks; vector< unsigned > bit, sum; SuccinctIndexableDictionary() = default; SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) { bit.assign(blocks, 0U); sum.assign(blocks, 0U); } void set(int k) { bit[k >> 5] |= 1U << (k & 31); } void build() { sum[0] = 0U; for(int i = 1; i < blocks; i++) { sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]); } } bool operator[](int k) { return (bool((bit[k >> 5] >> (k & 31)) & 1)); } int rank(int k) { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } int rank(bool val, int k) { return (val ? rank(k) : k - rank(k)); } }; /** * @brief Segment Tree(セグメント木) * @docs docs/segment-tree.md */ template< typename Monoid > struct SegmentTree { int n, sz; vector< Monoid > seg; Monoid M1; SegmentTree() = default; SegmentTree(int n, const Monoid &M1) : n(n), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } SegmentTree(const vector< Monoid > &v, const Monoid &M1) : SegmentTree((int) v.size(), M1) { build(v); } void build(const vector< Monoid > &v) { assert(n == (int) v.size()); for(int k = 0; k < n; k++) seg[k + sz] = v[k]; for(int k = sz - 1; k > 0; k--) { seg[k] = max(seg[2 * k + 0], seg[2 * k + 1]); // 書き方が分かりません... } } void set(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = max(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid get(int k) const { return seg[k + sz]; } Monoid operator[](const int &k) const { return get(k); } void apply(int k, const Monoid &x) { k += sz; seg[k] = max(seg[k], x); while(k >>= 1) { seg[k] = max(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid prod(int l, int r) const { Monoid L = M1, R = M1; for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) { if(l & 1) L = max(L, seg[l++]); if(r & 1) R = max(seg[--r], R); } return max(L, R); } Monoid all_prod() const { return seg[1]; } }; #line 3 "structure/wavelet/wavelet-matrix-point-add-rectangle-sum.cpp" /* * @brief Wavelet Matrix Point Add Rectangle Sum * @docs docs/wavelet-matrix-point-add-rectangle-sum.md */ template< typename T, int MAXLOG, typename D > struct WaveletMatrixPointApplyRectangleProd { size_t length; SuccinctIndexableDictionary matrix[MAXLOG]; SegmentTree< D > ds[MAXLOG]; vector< T > v; const D d0; int mid[MAXLOG]; WaveletMatrixPointApplyRectangleProd() = default; WaveletMatrixPointApplyRectangleProd(const vector< T > &v, const vector< D > &d, const D &d0) : length(v.size()), v(v), d0(d0) { assert(v.size() == d.size()); vector< int > l(length), r(length), ord(length); iota(begin(ord), end(ord), 0); vector< D > dd(length); for(int level = MAXLOG - 1; level >= 0; level--) { matrix[level] = SuccinctIndexableDictionary(length + 1); int left = 0, right = 0; for(int i = 0; i < length; i++) { if(((v[ord[i]] >> level) & 1)) { matrix[level].set(i); r[right++] = ord[i]; } else { l[left++] = ord[i]; } } mid[level] = left; matrix[level].build(); ord.swap(l); for(int i = 0; i < right; i++) { ord[left + i] = r[i]; } for(int i = 0; i < length; i++) { dd[i] = d[ord[i]]; } ds[level] = SegmentTree< D >(length, d0); } } pair< int, int > succ(bool f, int l, int r, int level) { return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f}; } // count d[i] s.t. (l <= i < r) && (v[i] < upper) D rect_max(int l, int r, T upper) { D ret = d0; for(int level = MAXLOG - 1; level >= 0; level--) { if(((upper >> level) & 1)) { auto nxt = succ(false, l, r, level); ret = max(ret, ds[level].prod(nxt.first, nxt.second)); l = l - nxt.first + mid[level]; r = r - nxt.second + mid[level]; } else { tie(l, r) = succ(false, l, r, level); } } return ret; } void point_add(int k, const D &x) { auto &y = v[k]; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = ((y >> level) & 1); k = matrix[level].rank(f, k) + mid[level] * f; if(ds[level][k] < x) ds[level].apply(k, x); } } }; int main() { int N; cin >> N; vector< tuple< int, int, int > > ds; ds.reserve(N + 1); for(int i = 0; i < N; i++) { int t, x, v; cin >> t >> x >> v; ds.emplace_back(t, x, v); } ds.emplace_back(0, 0, 0); sort(begin(ds), end(ds)); vector< int64 > dp(ds.size(), -infll); dp[0] = 0; vector< int > l, r; vector< pair< int, int > > m; l.reserve(N + 1); r.reserve(N + 1); m.reserve(N + 1); for(int i = 0; i < (int) ds.size(); i++) { auto[t, x, v]=ds[i]; l.emplace_back(t + x); r.emplace_back(t - x); m.emplace_back(x, i); } sort(begin(l), end(l)); l.erase(unique(begin(l), end(l)), end(l)); sort(begin(r), end(r)); r.erase(unique(begin(r), end(r)), end(r)); sort(begin(m), end(m)); vector< int > ldx(ds.size()), rdx(ds.size()), mdx(ds.size()); vector< int > ldh(ds.size()), rdh(ds.size()); vector< int64 > dv(ds.size(), -infll); for(int i = 0; i < (int) ds.size(); i++) { auto[t, x, v]=ds[i]; ldx[i] = lower_bound(begin(l), end(l), t + x) - begin(l); rdx[i] = lower_bound(begin(r), end(r), t - x) - begin(r); mdx[i] = lower_bound(begin(m), end(m), make_pair(x, i)) - begin(m); ldh[mdx[i]] = ldx[i]; rdh[mdx[i]] = rdx[i]; } WaveletMatrixPointApplyRectangleProd< int, 18, int64 > lseg(ldh, dv, -infll); WaveletMatrixPointApplyRectangleProd< int, 18, int64 > rseg(rdh, dv, -infll); lseg.point_add(mdx[0], 0); rseg.point_add(mdx[0], 0); int64 ret = 0; for(int i = 1; i < (int) ds.size(); i++) { auto[t2, x2, v2] = ds[i]; auto v = max(lseg.rect_max(mdx[i], m.size(), ldx[i] + 1), rseg.rect_max(0, mdx[i], rdx[i] + 1)); v += v2; chmax(ret, v); lseg.point_add(mdx[i], v); rseg.point_add(mdx[i], v); } cout << ret << "\n"; }