//#define NDEBUG #include #include #include #include namespace n91 { using i8 = std::int_fast8_t; using i32 = std::int_fast32_t; using i64 = std::int_fast64_t; using u8 = std::uint_fast8_t; using u32 = std::uint_fast32_t; using u64 = std::uint_fast64_t; using isize = std::ptrdiff_t; using usize = std::size_t; constexpr usize operator"" _z(unsigned long long x) noexcept { return static_cast(x); } class rep { const usize f, l; public: class itr { friend rep; usize i; constexpr itr(const usize x) noexcept : i(x) {} public: void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; constexpr rep(const usize first, const usize last) noexcept : f(first), l(last) {} constexpr itr begin() const noexcept { return itr(f); } constexpr itr end() const noexcept { return itr(l); } }; class revrep { const usize f, l; public: class itr { friend revrep; usize i; constexpr itr(usize x) noexcept : i(x) {} public: void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {} constexpr itr begin() const noexcept { return itr(l); } constexpr itr end() const noexcept { return itr(f); } }; template using vec_alias = std::vector; template auto md_vec(const usize n, const T &value) { return std::vector(n, value); } template auto md_vec(const usize n, Args... args) { return std::vector(n, md_vec(args...)); } template constexpr T difference(const T &a, const T &b) { return a < b ? b - a : a - b; } template T scan() { T ret; std::cin >> ret; return ret; } } // namespace n91 #include #include #include #include template class segment_tree { public: using value_structure = Monoid; using value_type = typename value_structure::value_type; using container_type = std::vector; using const_reference = typename container_type::const_reference; using size_type = typename container_type::size_type; protected: static size_type getsize(const size_type size) { size_type ret = 1; while (ret < size) ret <<= 1; return ret; } size_type size_; container_type tree; size_type base_size() const { return tree.size() >> 1; } void recalc(const size_type index) { tree[index] = value_structure::operation(tree[index << 1], tree[index << 1 | 1]); } public: segment_tree() : size_(0), tree() {} explicit segment_tree(const size_type size) : size_(size), tree(getsize(size) << 1, value_structure::identity()) {} template segment_tree(InputIterator first, InputIterator last) : size_(::std::distance(first, last)), tree() { const size_type cap = getsize(size_); tree.reserve(cap << 1); tree.resize(cap, value_structure::identity()); tree.insert(tree.end(), first, last); tree.resize(cap << 1, value_structure::identity()); for (size_type i = cap - 1; i; --i) recalc(i); } bool empty() const { return !size_; } size_type size() const { return size_; } const_reference operator[](const size_type index) const { assert(index < size()); return tree[index + base_size()]; } value_type fold(size_type first, size_type last) const { assert(first <= last); assert(first <= size()); assert(last <= size()); value_type ret_l = value_structure::identity(), ret_r = value_structure::identity(); for (first += base_size(), last += base_size(); first < last; first >>= 1, last >>= 1) { if (first & 1) ret_l = value_structure::operation(::std::move(ret_l), tree[first++]); if (last & 1) ret_r = value_structure::operation(tree[last - 1], ::std::move(ret_r)); } return value_structure::operation(::std::move(ret_l), ::std::move(ret_r)); } template size_type search_left(const F &f) const { value_type acc = value_structure::identity(); size_type i = 1; const size_type bs = base_size(); while (i < bs) { if (!f(value_structure::operation(acc, tree[i <<= 1]))) { acc = value_structure::operation(std::move(acc), tree[i++]); } } return std::min(size() - 1, i - bs); } template size_type search_right(const F &f) const { value_type acc = value_structure::identity(); size_type i = 1; const size_type bs = base_size(); while (i < bs) { if (!f(value_structure::operation(tree[i = i * static_cast(2) + static_cast(1)], acc))) { acc = value_structure::operation(tree[i--], std::move(acc)); } } return std::min(size() - 1, i - bs); } template void update(size_type index, const F &f) { assert(index < size()); index += base_size(); tree[index] = f(::std::move(tree[index])); while (index >>= 1) recalc(index); } }; #include #include template class max_monoid { public: using value_type = T; static value_type operation(const value_type &x, const value_type &y) { return ::std::max(x, y); } static value_type identity() { return ::std::numeric_limits::lowest(); } static value_type reverse(const value_type &x) { return x; } }; #include #include #include namespace n91 { void main_() { const u64 h = scan(); const u64 w = scan(); const usize n = scan(); struct query_type { u64 x, y, l; }; std::vector query(n); std::vector xs = {static_cast(0), w + static_cast(1)}, ys = {static_cast(0), h + static_cast(1)}; for (auto &e : query) { std::cin >> e.x >> e.y >> e.l; xs.push_back(e.x); ys.push_back(e.y); } std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); const auto xi = [&xs](const u64 x) { return static_cast(std::distance( xs.cbegin(), std::lower_bound(xs.cbegin(), xs.cend(), x))); }; const usize xn = xs.size(); const auto xf = [&w](const u64 x) { return w + static_cast(1) - x; }; std::sort(ys.begin(), ys.end()); ys.erase(std::unique(ys.begin(), ys.end()), ys.end()); const auto yi = [&ys](const u64 y) { return static_cast(std::distance( ys.cbegin(), std::lower_bound(ys.cbegin(), ys.cend(), y))); }; const usize yn = ys.size(); const auto yf = [&h](const u64 y) { return h + static_cast(1) - y; }; segment_tree> u(xn), d(xn), l(yn), r(yn); for (const auto &q : query) { if (q.y == static_cast(0)) { const u64 dlim = yf(d[xi(q.x)]); const u64 llim = ys[l.search_left([&](const u64 v) { return v >= q.x; })]; const u64 rlim = ys[r.search_left([&](const u64 v) { return v >= xf(q.x); })]; const u64 next = u[xi(q.x)] + q.l; if (next < llim && next < rlim && next < dlim) { u.update(xi(q.x), [&](auto) { return next; }); } else if (dlim <= llim && dlim <= rlim) { u.update(xi(q.x), [&](auto) { return static_cast(0); }); d.update(xi(q.x), [&](auto) { return static_cast(0); }); } else if (llim < rlim) { u.update(xi(q.x), [&](auto) { return static_cast(0); }); l.update(yi(llim), [&](auto) { return static_cast(0); }); } else { u.update(xi(q.x), [&](auto) { return static_cast(0); }); r.update(yi(rlim), [&](auto) { return static_cast(0); }); } } else if (q.y == h + static_cast(1)) { const u64 ulim = yf(u[xi(q.x)]); const u64 llim = yf(ys[l.search_right([&](const u64 v) { return v >= q.x; })]); const u64 rlim = yf(ys[r.search_right([&](const u64 v) { return v >= xf(q.x); })]); const u64 next = d[xi(q.x)] + q.l; if (next < llim && next < rlim && next < ulim) { d.update(xi(q.x), [&](auto) { return next; }); } else if (ulim <= llim && ulim <= rlim) { d.update(xi(q.x), [&](auto) { return static_cast(0); }); u.update(xi(q.x), [&](auto) { return static_cast(0); }); } else if (llim < rlim) { d.update(xi(q.x), [&](auto) { return static_cast(0); }); l.update(yi(yf(llim)), [&](auto) { return static_cast(0); }); } else { d.update(xi(q.x), [&](auto) { return static_cast(0); }); r.update(yi(yf(rlim)), [&](auto) { return static_cast(0); }); } } else if (q.x == static_cast(0)) { const u64 rlim = xf(r[yi(q.y)]); const u64 ulim = xs[u.search_left([&](const u64 v) { return v >= q.y; })]; const u64 dlim = xs[d.search_left([&](const u64 v) { return v >= yf(q.y); })]; const u64 next = l[yi(q.y)] + q.l; if (next < ulim && next < dlim && next < rlim) { l.update(yi(q.y), [&](auto) { return next; }); } else if (rlim <= ulim && rlim <= dlim) { l.update(yi(q.y), [&](auto) { return static_cast(0); }); r.update(yi(q.y), [&](auto) { return static_cast(0); }); } else if (ulim < dlim) { l.update(yi(q.y), [&](auto) { return static_cast(0); }); u.update(xi(ulim), [&](auto) { return static_cast(0); }); } else { l.update(yi(q.y), [&](auto) { return static_cast(0); }); d.update(xi(dlim), [&](auto) { return static_cast(0); }); } } else { const u64 llim = xf(l[yi(q.y)]); const u64 ulim = xf(xs[u.search_right([&](const u64 v) { return v >= q.y; })]); const u64 dlim = xf(xs[r.search_right([&](const u64 v) { return v >= yf(q.y); })]); const u64 next = r[yi(q.y)] + q.l; if (next < ulim && next < dlim && next < llim) { r.update(yi(q.y), [&](auto) { return next; }); } else if (llim <= ulim && llim <= dlim) { r.update(yi(q.y), [&](auto) { return static_cast(0); }); l.update(yi(q.y), [&](auto) { return static_cast(0); }); } else if (ulim < dlim) { r.update(yi(q.y), [&](auto) { return static_cast(0); }); u.update(xi(xf(ulim)), [&](auto) { return static_cast(0); }); } else { r.update(yi(q.y), [&](auto) { return static_cast(0); }); d.update(xi(xf(dlim)), [&](auto) { return static_cast(0); }); } } } u64 ans = static_cast(0); for (const auto i : rep(0_z, xn)) { ans += u[i]; ans += d[i]; } for (const auto i : rep(0_z, yn)) { ans += l[i]; ans += r[i]; } std::cout << ans << std::endl; } } // namespace n91 int main() { n91::main_(); return 0; }