#1107455 (C++23) No.3214 small square

• 問題: No.3214 small square
• ユーザー: dp_ijk
• 提出日時: 2025-07-25 22:49:21
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 8,710 bytes
• コンパイル時間: 2,258 ms
• コンパイル使用メモリ: 183,276 KB
• 実行使用メモリ: 288,664 KB
• 最終ジャッジ日時: 2025-07-25 22:49:29
• 合計ジャッジ時間: 7,597 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 10 TLE * 1 -- * 29

ソースコード

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
struct IOSetup {
    IOSetup() {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(15);
        std::cerr << std::fixed << std::setprecision(8);
    }
};
IOSetup iosetup;
using int128_t = __int128;
using uint128_t = unsigned __int128;
template <typename T>
constexpr auto rep_iota_impl(T start, T stop) noexcept {
    return std::views::iota(start, (start < stop ? stop : start));
}
template <typename T = int64_t>
constexpr auto rep_impl(auto start, auto stop) noexcept {
    return rep_iota_impl<T>(start, stop);
}
template <typename T = int64_t>
constexpr auto rep_impl(auto stop) noexcept {
    return rep_iota_impl<T>(0, stop);
}
template <class... Ts>
inline void read(Ts&... ts) {
    (std::cin >> ... >> ts);
}
template <class T, class U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
using std::vector;
template <typename X>
struct MAdd {
    using ll = int64_t;
    using T = X;
    static constexpr T op(const T& x, const T& y) noexcept { return x + y; }
    static constexpr T inverse(const T& x) noexcept { return -x; }
    static constexpr T power(const T& x, ll n) noexcept { return T{x} * n; }
    static constexpr T unit() noexcept { return T{}; }
    static constexpr bool is_unit(const T& x) noexcept { return x == T{}; }
    static constexpr bool commutative = 1;
    static constexpr bool invertible = 1;
};
template <typename T>
void put(const T& t) {
    std::cout << t;
}
template <typename... Ts>
void print(const Ts&... ts) {
    put(ts...);
    std::cout << "\n";
}
using std::cin;
using std::cout;
using std::map;
using std::pair;
using std::set;
using std::string;
using std::tuple;
using std::vector;
using ll = int64_t;
template <typename MX_, typename MA_, auto operate, auto default_factory>
struct DynamicLazySegTree {
    public:
    using ll = int64_t;
    using MX = MX_;
    using MA = MA_;
    using X = typename MX::T;
    using A = typename MA::T;
    using value_type = typename MX::T;
    static_assert(std::is_invocable_v<decltype(operate), X, A, ll>);
    struct Node;
    using Tree = Node*;
    struct Node {
        X val;
        A lazy;
        Tree left, right;
        Node()
            : val(MX::unit()),
              lazy(MA::unit()),
              left(nullptr),
              right(nullptr) {}
    };
    auto _new(ll nL, ll nR) {
        auto t = new Node();
        t->val = default_factory(nL, nR);
        return t;
    }
    inline void _del(Tree t) { delete t; }
    void _delete_subtree(Tree t) {
        if (!t) return;
        _delete_subtree(t->left);
        _delete_subtree(t->right);
        _del(t);
    }
    void clear() {
        _delete_subtree(root);
        root = nullptr;
    }
    Tree root;
    const ll maxlen;
    DynamicLazySegTree() = default;
    explicit DynamicLazySegTree(ll maxlen_)
        : root(_new(0, maxlen_)),
          maxlen(maxlen_) {
        assert(maxlen_ >= 0);
    }

    private:
    void apply_subtree(Tree t, const A& a, const ll nL, const ll nR) const {
        assert(nL < nR);
        t->val = operate(t->val, a, nR - nL);
        t->lazy = MA::op(t->lazy, a);
    }
    void push_lazy(Tree t, ll nL, ll nR) {
        assert(nR - nL >= 2);
        if (nR - nL == 1) return;
        assert(t);
        if (t->lazy == MA::unit()) return;
        ll m = std::midpoint(nL, nR);
        if (!t->left) t->left = _new(nL, m);
        if (!t->right) t->right = _new(m, nR);
        apply_subtree(t->left, t->lazy, nL, m);
        apply_subtree(t->right, t->lazy, m, nR);
        t->lazy = MA::unit();
    }
    void update(Tree t, ll nL, ll nR) {
        assert(t);
        assert(nR - nL >= 2);
        if (nR - nL == 1) return;
        ll m = std::midpoint(nL, nR);
        X vL = t->left ? t->left->val : default_factory(nL, m);
        X vR = t->right ? t->right->val : default_factory(m, nR);
        t->val = MX::op(vL, vR);
    }

    public:
    X fold(ll l, ll r) { return _fold(l, r, MA::unit(), root, 0, maxlen); }
    X fold_all() { return fold(0, maxlen); }
    X _fold(ll l, ll r, const A lazy, Tree t, const ll nL, const ll nR) {
        chmax(l, nL);
        chmin(r, nR);
        if (not(l < r)) return MX::unit();
        if (!t) { return operate(default_factory(l, r), lazy, r - l); }
        if (l == nL && r == nR) { return operate(t->val, lazy, r - l); }
        ll m = std::midpoint(nL, nR);
        A nlazy = MA::op(t->lazy, lazy);
        X vL = _fold(l, r, nlazy, t->left, nL, m);
        X vR = _fold(l, r, nlazy, t->right, m, nR);
        return MX::op(vL, vR);
    }
    void apply(const ll l, const ll r, const A& a) { _apply(l, r, a, root, 0, maxlen); }
    Tree _apply(ll l, ll r, const A a, Tree t, const ll nL, const ll nR) {
        if (a == MA::unit()) return t;
        if (!t) t = _new(nL, nR);
        chmax(l, nL);
        chmin(r, nR);
        if (not(l < r)) return t;
        if (l == nL && r == nR) {
            apply_subtree(t, a, nL, nR);
            return t;
        }
        push_lazy(t, nL, nR);
        ll m = std::midpoint(nL, nR);
        t->left = _apply(l, r, a, t->left, nL, m);
        t->right = _apply(l, r, a, t->right, m, nR);
        update(t, nL, nR);
        return t;
    }
    void set(const ll i, const X& x) {
        assert(0 <= i && i < maxlen);
        root = _set(i, x, root, 0, maxlen);
    }
    Tree _set(const ll i, const X& x, Tree t, const ll nL, const ll nR) {
        if (nR - nL == 1) {
            t->val = x;
            t->lazy = MA::unit();
            return t;
        }
        push_lazy(t, nL, nR);
        ll m = std::midpoint(nL, nR);
        if (!t->left) t->left = _new(nL, m);
        if (!t->right) t->right = _new(m, nR);
        if (i < m) {
            t->left = _set(i, x, t->left, nL, m);
        } else {
            t->right = _set(i, x, t->right, m, nR);
        }
        update(t, nL, nR);
        return t;
    }

    X operator[](ll k) const { return fold(k, k + 1); }
    X get(ll k) const { return fold(k, k + 1); }
};
constexpr int64_t INF = 23e17;
template <typename X, X INF>
struct MMax {
    using T = X;
    static constexpr T op(T x, T y) { return (x < y) ? y : x; }
    static constexpr T unit() { return -INF; }
    static constexpr bool is_unit(const T& x) { return x == -INF; }
    static constexpr bool commutative = true;
    static constexpr bool idempotent = true;
};
ll operate(ll M, ll a, [[maybe_unused]] ll sz) { return M + a; }
ll default_factory(ll l, ll r) { return 0; }
struct Point {
    ll x, y, v;
};
ll resolve(ll N, ll P, ll Q, vector<Point> XYV) {
    ll minY = INF;
    for (const auto i : rep_impl((N))) {
        auto [x, y, v] = XYV[i];
        chmin(minY, y);
    }
    for (const auto i : rep_impl((N))) {
        auto [x, y, v] = XYV[i];
        XYV[i] = {x, y - minY + (Q - 1), v};
    }
    map<ll, vector<Point>> todo;
    for (const auto i : rep_impl((N))) {
        auto [x, y, v] = XYV[i];
        todo[x].push_back({x, y, v});
    }
    set<ll> T;
    for (auto& [x, _] : todo) {
        T.insert(x - (P - 1));
        T.insert(x + 1);
    }
    auto seg = DynamicLazySegTree<MMax<ll, INF>, MAdd<ll>, operate, default_factory>(1e10);
    ll res = 0;
    for (auto t : T) {
        for (auto [x, y, v] : todo[t + (P - 1)]) {
            assert(0 <= y - (Q - 1));
            seg.apply(y - (Q - 1), y + 1, v);
        }
        for (auto [x, y, v] : todo[t - 1]) {
            assert(0 <= y - (Q - 1));
            seg.apply(y - (Q - 1), y + 1, -v);
        }
        ll nres = seg.fold_all();
        chmax(res, nres);
    }
    seg.clear();
    return res;
}
int main() {
    int64_t N, A;
    read(N, A);
    vector<Point> XYV(N);
    for (const auto i : rep_impl((N))) {
        int64_t x, y, v;
        read(x, y, v);
        XYV[i] = {x, y, v};
    }
    ll res = 0;
    for (const auto P : rep_impl((A), (A + 2)))
        for (const auto Q : rep_impl((A), (A + 2)))
            chmax(res, resolve(N, P, Q, XYV));
    print(res);
}