#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } const std::vector> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); } template std::pair operator+(const std::pair &l, const std::pair &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template std::pair operator-(const std::pair &l, const std::pair &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template std::vector sort_unique(std::vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template int arglb(const std::vector &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template int argub(const std::vector &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template IStream &operator>>(IStream &is, std::vector &vec) { for (auto &v : vec) is >> v; return is; } template OStream &operator<<(OStream &os, const std::vector &vec); template OStream &operator<<(OStream &os, const std::array &arr); template OStream &operator<<(OStream &os, const std::unordered_set &vec); template OStream &operator<<(OStream &os, const pair &pa); template OStream &operator<<(OStream &os, const std::deque &vec); template OStream &operator<<(OStream &os, const std::set &vec); template OStream &operator<<(OStream &os, const std::multiset &vec); template OStream &operator<<(OStream &os, const std::unordered_multiset &vec); template OStream &operator<<(OStream &os, const std::pair &pa); template OStream &operator<<(OStream &os, const std::map &mp); template OStream &operator<<(OStream &os, const std::unordered_map &mp); template OStream &operator<<(OStream &os, const std::tuple &tpl); template OStream &operator<<(OStream &os, const std::vector &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::array &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } template std::istream &operator>>(std::istream &is, std::tuple &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template OStream &operator<<(OStream &os, const std::tuple &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } template OStream &operator<<(OStream &os, const std::unordered_set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::deque &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::pair &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template OStream &operator<<(OStream &os, const std::map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif template class wavelet_matrix { class bit_vector { static constexpr int WSIZE = 64; int n = 0; int cnt0 = 0; std::vector bits; std::vector count_cumsum; // need build() public: bit_vector(int n_) : n(n_), cnt0(n_) { assert(n >= 0); bits.assign((n + WSIZE - 1) / WSIZE, 0); } int size() const { return n; } void set(int i) { assert(0 <= i and i < n); bits[i / WSIZE] |= (1ULL << (i % WSIZE)); } void reset(int i) { assert(0 <= i and i < n); bits[i / WSIZE] &= ~(1ULL << (i % WSIZE)); } void build() { cnt0 = n; for (int i = 0; i < (int)bits.size(); ++i) cnt0 -= std::popcount(bits[i]); count_cumsum.assign(bits.size(), 0); for (int i = 1; i < (int)bits.size(); ++i) { count_cumsum[i] = count_cumsum[i - 1] + std::popcount(bits[i - 1]); } } int count0() const { return cnt0; } int count1() const { return n - cnt0; } // get i-th bit bool access(int i) const { assert(0 <= i and i < n); return bits[i / WSIZE] & (1ULL << (i % WSIZE)); } // count of 0s in [0, i) int rank0(int i) const { assert(0 <= i and i <= n); return i - rank1(i); } // count of 1s in [0, i) int rank1(int i) const { assert(0 <= i and i <= n); if (i == n) return count1(); return count_cumsum[i / WSIZE] + std::popcount(bits[i / WSIZE] & ((1ULL << (i % WSIZE)) - 1)); } // get the position of i-th element after stable sort int sorted_pos(int i) const { return access(i) ? (rank1(i) + count0()) : rank0(i); } template friend OStream &operator<<(OStream &os, const bit_vector &bv) { os << "bit_vector[" << bv.n << "]: "; for (int i = 0; i < bv.n; ++i) { os << (bv.bits[i / WSIZE] & (1ULL << (i % WSIZE)) ? '1' : '0'); } os << " (cnt0: " << bv.cnt0 << ")"; return os; } }; std::vector bits; std::vector> points; std::vector distinct_ys; int to_index_x(Int x) const { return std::lower_bound(points.cbegin(), points.cend(), std::make_pair(x, Int{}), [](const auto &l, const auto &r) { return l.first < r.first; }) - points.cbegin(); } int to_index_y(Int y) const { return std::lower_bound(distinct_ys.cbegin(), distinct_ys.cend(), y) - distinct_ys.cbegin(); } bool is_built() const { return !bits.empty(); } public: wavelet_matrix() = default; wavelet_matrix(const std::vector &ys) { for (int x = 0; x < (int)ys.size(); ++x) { assert(ys[x] >= 0); add_point(x, ys[x]); } build(); } void add_point(Int x, Int y) { assert(bits.empty()); // confirm that build() is not called yet points.emplace_back(x, y); distinct_ys.emplace_back(y); } void build() { std::sort(points.begin(), points.end()); points.erase(std::unique(points.begin(), points.end()), points.end()); std::sort(distinct_ys.begin(), distinct_ys.end()); distinct_ys.erase(std::unique(distinct_ys.begin(), distinct_ys.end()), distinct_ys.end()); int d = 1; while ((1 << d) < (int)distinct_ys.size()) ++d; bits.assign(d, bit_vector(N())); std::vector a; for (auto p : points) a.push_back(to_index_y(p.second)); auto nxt = a; for (int d = D() - 1; d >= 0; --d) { for (int i = 0; i < N(); ++i) { if ((a[i] >> d) & 1) bits[d].set(i); } bits[d].build(); for (int i = 0; i < N(); ++i) nxt[bits[d].sorted_pos(i)] = a[i]; std::swap(a, nxt); } } int N() const { return points.size(); } int D() const { return bits.size(); } // get v_i int index_access(int i) const { assert(0 <= i and i < N()); assert(is_built()); int ret = 0; for (int d = D() - 1; d >= 0; --d) { ret |= (int)bits[d].access(i) << d; i = bits[d].sorted_pos(i); } return ret; } Int access(int i) const { assert(0 <= i and i < N()); assert(is_built()); return distinct_ys.at(index_access(i)); } // callback(d, i) means "update d-th segment's i-th element" void index_apply(int i, auto callback) const { assert(0 <= i and i < N()); assert(is_built()); for (int d = D() - 1; d >= 0; --d) { i = bits[d].sorted_pos(i); callback(d, i); } } // Update weight associated to point (x, y) // callback(d, i) means "update d-th segment's i-th element" void apply(Int x, Int y, auto callback) const { const int i = std::lower_bound(points.cbegin(), points.cend(), std::make_pair(x, y)) - points.cbegin(); assert(i < N() and points[i] == std::make_pair(x, y)); index_apply(i, callback); } void index_prod(int l, int r, int yr, auto callback) const { assert(0 <= l and l <= r and r <= N()); assert(0 <= yr and yr <= (int)distinct_ys.size()); assert(is_built()); if (yr & (1 << D())) { const int d = D() - 1; const int l0 = bits[d].rank0(l), r0 = bits[d].rank0(r); callback(d, l0, r0); const int l1 = bits[d].rank1(l) + bits[d].count0(); const int r1 = bits[d].rank1(r) + bits[d].count0(); callback(d, l1, r1); return; } for (int d = D() - 1; d >= 0; --d) { if (l == r) break; const int l0 = bits[d].rank0(l), r0 = bits[d].rank0(r); if ((yr >> d) & 1) { callback(d, l0, r0); // l = bits[d].rank1(l) + bits[d].count0(); l += bits[d].count0() - l0; // r = bits[d].rank1(r) + bits[d].count0(); r += bits[d].count0() - r0; } else { l = l0, r = r0; } } } // Get product of weights associated to elements in [xl, xr) * [-inf, yr) // callback(d, l, r) means "use d-th segment's [l, r) elements" void prod(Int xl, Int xr, Int yr, auto callback) const { index_prod(to_index_x(xl), to_index_x(xr), to_index_y(yr), callback); } // Get k-th smallest v_i, i in [l, r) (0-indexed, duplicates are counted)] int index_kth_smallest(int l, int r, int k) const { assert(0 <= l and l <= r and r <= N()); assert(0 <= k and k < r - l); assert(is_built()); int ret = 0; for (int d = D() - 1; d >= 0; --d) { const int l0 = bits[d].rank0(l), r0 = bits[d].rank0(r); if (k < r0 - l0) { l = l0, r = r0; } else { k -= r0 - l0; ret |= 1 << d; l = bits[d].rank1(l) + bits[d].count0(); r = bits[d].rank1(r) + bits[d].count0(); } } return ret; } // Get k-th largest v_i, i in [l, r) (0-indexed, duplicates are counted) int index_kth_largest(int l, int r, int k) const { assert(0 <= l and l <= r and r <= N()); assert(0 <= k and k < r - l); return index_kth_smallest(l, r, (r - l - 1) - k); } // count i s.t. i in [l, r) and v_i < upper_bound int index_range_freq(int l, int r, int upper_bound) const { assert(0 <= l and l <= r and r <= N()); assert(is_built()); if (upper_bound <= 0) return 0; if (upper_bound >= (int)distinct_ys.size()) return r - l; int ret = 0; for (int d = D() - 1; d >= 0; --d) { const int l0 = bits[d].rank0(l), r0 = bits[d].rank0(r); if ((upper_bound >> d) & 1) { ret += r0 - l0; l = bits[d].rank1(l) + bits[d].count0(); r = bits[d].rank1(r) + bits[d].count0(); } else { l = l0, r = r0; } } return ret; } // Get k-th smallest y in [xl, xr) (0-indexed, duplicates are counted) std::optional kth_smallest(Int xl, Int xr, int k) const { const int l = to_index_x(xl), r = to_index_x(xr); if (k < 0 or k >= r - l) return std::nullopt; return distinct_ys.at(index_kth_smallest(l, r, k)); } // Get k-th largest y in [xl, xr) (0-indexed, duplicates are counted) std::optional kth_largest(Int xl, Int xr, int k) const { const int l = to_index_x(xl), r = to_index_x(xr); if (k < 0 or k >= r - l) return std::nullopt; return distinct_ys.at(index_kth_largest(l, r, k)); } // count points in [xl, xr) * [-inf, yr) int range_freq(Int xl, Int xr, Int yr) const { return index_range_freq(to_index_x(xl), to_index_x(xr), to_index_y(yr)); } // max v_i s.t. i in [l, r), v_i < upper_bound std::optional index_prev_value(int l, int r, int upper_bound) const { assert(0 <= l and l <= r and r <= N()); assert(is_built()); if (upper_bound <= 0) return std::nullopt; const int n = index_range_freq(l, r, upper_bound); return n == 0 ? std::nullopt : index_kth_smallest(l, r, n - 1); } // max y s.t. x in [xl, xr), y < yr std::optional prev_value(Int xl, Int xr, Int yr) const { const int l = to_index_x(xl), r = to_index_x(xr), ub = to_index_y(yr); const auto idx = index_prev_value(l, r, ub); return idx ? distinct_ys.at(*idx) : std::nullopt; } // min v_i s.t. i in [l, r), v_i >= lower_bound std::optional index_next_value(int l, int r, int lower_bound) const { assert(0 <= l and l <= r and r <= N()); assert(is_built()); if (lower_bound >= (int)distinct_ys.size()) return std::nullopt; const int n = index_range_freq(l, r, lower_bound); return n >= (r - l) ? std::nullopt : index_kth_smallest(l, r, n); } // min y s.t. x in [xl, xr), y >= yl std::optional next_value(Int l, Int r, Int yl) const { const int xl = to_index_x(l), xr = to_index_x(r), yl_idx = to_index_y(yl); const auto idx = index_next_value(xl, xr, yl_idx); return idx ? distinct_ys.at(*idx) : std::nullopt; } }; #include lint op(lint l, lint r) { return max(l, r); } lint e() { return 0; } using F = lint; lint mapping(F f, lint x) { return f + x; } lint composition(F f, F g) { return f + g; } lint id() { return 0; } lint solve(const vector> &points, int Ax, int Hy) { vector xs, ys; for (auto [x, y, w] : points) { xs.push_back(x); xs.push_back(x + 1); xs.push_back(x + Ax - 1); xs.push_back(x + Ax); xs.push_back(x - Ax); xs.push_back(x - Ax + 1); ys.push_back(y); ys.push_back(y + Hy); } xs = sort_unique(xs); ys = sort_unique(ys); // map> events; vector>> removes(ys.size()), adds(ys.size()); for (auto [x, y, w] : points) { // events[y].emplace_back(x, w); // events[y + Hy].emplace_back(x, -w); const int lx = arglb(xs, x); const int rx = arglb(xs, x + Ax); adds.at(arglb(ys, y)).emplace_back(lx, rx, w); removes.at(arglb(ys, y + Hy)).emplace_back(lx, rx, -w); } lint ret = 0; atcoder::lazy_segtree seg(xs.size()); REP(idx, ys.size()) { for (auto [lx, rx, w] : adds.at(idx)) seg.apply(lx, rx, w); chmax(ret, seg.all_prod()); for (auto [lx, rx, w] : removes.at(idx)) seg.apply(lx, rx, w); chmax(ret, seg.all_prod()); } return ret; } int main() { int N, A; cin >> N >> A; vector xs; vector> points(N); for (auto &[x, y, v] : points) { cin >> x >> y >> v; } lint ret = 0; for (int dx : {0, 1}) { chmax(ret, solve(points, A + dx, A)); } cout << ret << '\n'; }