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

提出ソース
結果

問題	No.3214 small square
ユーザー	dp_ijk
提出日時	2025-07-25 23:13:39
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2,138 ms / 3,000 ms
コード長	17,089 bytes
コンパイル時間	2,535 ms
コンパイル使用メモリ	194,800 KB
実行使用メモリ	52,076 KB
最終ジャッジ日時	2025-07-25 23:14:42
合計ジャッジ時間	56,737 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 40
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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 <typename T = int64_t>
constexpr auto rep_impl(auto start, auto stop, auto step) noexcept {
    struct Rep {
        struct Iter {
            T cur;
            const T stop;
            const T step;
            constexpr Iter& operator++() noexcept {
                cur += step;
                return *this;
            }
            constexpr T operator*() const noexcept { return cur; }
            constexpr bool operator==(std::default_sentinel_t) const noexcept {
                return (step > 0) ? cur >= stop : cur <= stop;
            }
        };
        Iter iter;
        constexpr Rep(T start, T stop, T step) noexcept
            : iter{start, stop, step} {
            assert(step != 0);
        }
        constexpr Iter begin() const noexcept { return iter; }
        constexpr std::default_sentinel_t end() const noexcept { return {}; }
    };
    return Rep(start, stop, step);
}
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;
}
template <typename T>
void unique_inplace(std::vector<T>& A) {
    if (!std::is_sorted(A.begin(), A.end())) { std::sort(A.begin(), A.end()); }
    A.erase(std::unique(A.begin(), A.end()), A.end());
}
using std::vector;
template <typename T, typename U>
vector<T> cumsum(vector<T>& A, U initial) {
    vector<T> res(A.size() + 1);
    res[0] = initial;
    for (const auto i : rep_impl((1), (res.size())))
        res[i] = res[i - 1] + A[i - 1];
    return res;
}
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;
using std::vector;
template <typename Data>
struct ElementProxy {
    using T = Data::value_type;

    private:
    Data& data;
    const int index;

    public:
    constexpr ElementProxy(Data& data_, int index) noexcept
        : data(data_),
          index(index) {}
    operator T() const { return data.get(index); }
    ElementProxy& operator=(const T& x) {
        data.set(index, x);
        return *this;
    }
    ElementProxy& operator+=(const T& x) {
        data.set(index, data.get(index) + x);
        return *this;
    }
    ElementProxy& operator-=(const T& x) {
        data.set(index, data.get(index) - x);
        return *this;
    }
    ElementProxy& operator*=(const T& x) {
        data.set(index, data.get(index) * x);
        return *this;
    }
    ElementProxy& operator/=(const T& x) {
        data.set(index, data.get(index) / x);
        return *this;
    }
    template <typename D = Data>
        requires requires { typename D::lazy_type; }
    ElementProxy& apply(const typename D::lazy_type& a) {
        data.apply(index, a);
        return *this;
    }
    template <typename D = Data>
        requires requires { typename D::lazy_type; }
    ElementProxy& operator%=(const typename D::lazy_type& a) {
        data.apply(index, index + 1, a);
        return *this;
    }
};
template <typename MX_, typename MA_, auto operate>
struct LazySegTree {
    using ll = int64_t;
    using MX = MX_;
    using MA = MA_;
    using X = typename MX::T;
    using A = typename MA::T;
    using value_type = X;
    using lazy_type = A;
    constexpr static bool action_commutative = []() {
        if constexpr (requires { MA::commutative; }) { return MA::commutative; }
        return false;
    }();
    constexpr static bool is_zero(const A& a) {
        if constexpr (requires { &MA::is_unit; }) {
            return MA::is_unit(a);
        } else {
            return a == MA::unit();
        }
    }
    int N, log, size;
    vector<X> data;
    vector<A> lazy;
    LazySegTree() {}
    LazySegTree(ll N) { build(N); }
    LazySegTree(ll N, auto f) { build(N, f); }
    template <typename S>
    LazySegTree(const vector<S>& A) {
        build(A);
    }
    void build(ll N) {
        build(N, [](ll i) -> X { return MX::unit(); });
    }
    template <typename S>
    void build(const vector<S>& A) {
        build(A.size(), [&](ll i) -> X { return A[i]; });
    }
    void build(ll N_, auto f) {
        N = N_, log = 1;
        while ((1 << log) < N)
            ++log;
        size = 1 << log;
        data.assign(size << 1, MX::unit());
        lazy.assign(size, MA::unit());
        for (const auto i : rep_impl((N)))
            data[size + i] = f(i);
        for (const auto i : rep_impl((size - 1), (0), (-1)))
            update(i);
    }
    inline void operate_inplace(int v, A a) {
        assert(1 <= v && v < size * 2);
        if constexpr (std::is_invocable_v<decltype(operate), X, A>) {
            data[v] = operate(data[v], a);
        } else {
            int bitlen = std::bit_width(uint32_t(v));
            ll width = ll(1) << (log - (bitlen - 1));
            data[v] = operate(data[v], a, width);
        }
    }
    inline void apply_subtree(int v, A a) {
        assert(1 <= v && v < size * 2);
        operate_inplace(v, a);
        if (v < size) lazy[v] = MA::op(lazy[v], a);
    }
    template <bool has_lazy = 1>
    inline void update(int p) {
        assert(1 <= p && p < size);
        data[p] = MX::op(data[p << 1], data[p << 1 | 1]);
        if constexpr (action_commutative && has_lazy) { operate_inplace(p, lazy[p]); }
    }
    inline void push_lazy(int p) {
        if (p == 0) return;
        assert(1 <= p && p < size);
        if (is_zero(lazy[p])) return;
        apply_subtree(p << 1, lazy[p]);
        apply_subtree(p << 1 | 1, lazy[p]);
        lazy[p] = MA::unit();
    }
    inline void rectify_leaf(int j) {
        assert(size <= j && j < size * 2);
        for (int h = log; h >= 1; h--)
            push_lazy(j >> h);
    }
    void set(ll i, X x) {
        assert(0 <= i && i < N);
        int j = i + size;
        rectify_leaf(j);
        data[j] = x;
        for (int h = 1; h <= log; h++)
            update<0>(j >> h);
    }
    X get(ll i) {
        assert(0 <= i && i < N);
        int j = i + size;
        rectify_leaf(j);
        return data[j];
    }
    vector<X> get_all() {
        for (const auto i : rep_impl((1), (size)))
            push_lazy(i);
        return {data.begin() + size, data.begin() + size + N};
    }
    auto copy() const {
        LazySegTree<MX, MA, operate> res(N);
        res.data = data;
        res.lazy = lazy;
        return res;
    }
    vector<X> to_vector() const { return copy().get_all(); }
    X fold(ll L, ll R) {
        chmax(L, 0);
        chmin(R, N);
        if (not(L < R)) return MX::unit();
        assert(0 <= L && L < R && R <= N);
        if (R == N) R = size;
        L += size, R += size;
        for (int i = log; i >= 1; i--) {
            if (((L >> i) << i) != L) push_lazy(L >> i);
            if (((R >> i) << i) != R) push_lazy((R - 1) >> i);
        }
        X vL = MX::unit(), vR = MX::unit();
        while (L < R) {
            if (L & 1) vL = MX::op(vL, data[L++]);
            if (R & 1) vR = MX::op(data[--R], vR);
            L >>= 1, R >>= 1;
        }
        return MX::op(vL, vR);
    }
    X fold_all() const { return data[1]; }
    void apply(int L, int R, A a) {
        chmax(L, 0);
        chmin(R, N);
        if (not(L < R)) return;
        assert(0 <= L && L < R && R <= N);
        if (R == N) R = size;
        L += size, R += size;
        const std::pair<int, int> backup = {L, R};
        if constexpr (!action_commutative) {
            for (int i = log; i >= 1; i--) {
                if (((L >> i) << i) != L) push_lazy(L >> i);
                if (((R >> i) << i) != R) push_lazy((R - 1) >> i);
            }
        }
        while (L < R) {
            if (L & 1) apply_subtree(L++, a);
            if (R & 1) apply_subtree(--R, a);
            L >>= 1, R >>= 1;
        }
        std::tie(L, R) = backup;
        for (int i = 1; i <= log; i++) {
            if (((L >> i) << i) != L) { update(L >> i); }
            if (((R >> i) << i) != R) { update((R - 1) >> i); }
        }
    }
    void apply_all(A a) { apply(0, size, a); }
    int max_right(int l, auto is_ok) {
        assert(0 <= l && l <= N);
        assert(is_ok(MX::unit()));
        if (l == N) return N;
        l += size;
        for (int i = log; i >= 1; i--)
            push_lazy(l >> i);
        X sm = MX::unit();
        do {
            while (l % 2 == 0)
                l >>= 1;
            if (!is_ok(MX::op(sm, data[l]))) {
                while (l < size) {
                    push_lazy(l);
                    l = (2 * l);
                    if (is_ok(MX::op(sm, data[l]))) { sm = MX::op(sm, data[l++]); }
                }
                return l - size;
            }
            sm = MX::op(sm, data[l++]);
        } while ((l & -l) != l);
        return N;
    }
    int min_left(int r, auto is_ok) {
        assert(0 <= r && r <= N);
        assert(is_ok(MX::unit()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--)
            push_lazy((r - 1) >> i);
        X sm = MX::unit();
        do {
            r--;
            while (r > 1 && (r % 2))
                r >>= 1;
            if (!is_ok(MX::op(data[r], sm))) {
                while (r < size) {
                    push_lazy(r);
                    r = (2 * r + 1);
                    if (is_ok(MX::op(data[r], sm))) { sm = MX::op(data[r--], sm); }
                }
                return r + 1 - size;
            }
            sm = MX::op(data[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    class RangeProxy {
        private:
        LazySegTree<MX, MA, operate>& seg;
        const int L, R;

        public:
        explicit RangeProxy(LazySegTree<MX, MA, operate>& seg, int L, int R)
            : seg(seg),
              L(L),
              R(R) {}
        RangeProxy& operator%=(const A& a) {
            seg.apply(L, R, a);
            return *this;
        }
        operator X() && { return seg.fold(L, R); }
        operator X() & { return seg.fold(L, R); }
    };

    public:
    auto operator()(int index) {
        assert(0 <= index && index < N);
        return ElementProxy<LazySegTree<MX, MA, operate>>(*this, index);
    }
    RangeProxy operator()(int L, int R) { return RangeProxy(*this, L, R); }
    X operator[](std::pair<int, int> LR) {
        auto [L, R] = LR;
        return fold(L, R);
    }
    X operator[](int index) {
        assert(0 <= index && index < N);
        return get(index);
    }
};
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) { return M + a; }
using std::pair;
using std::tuple;
using std::vector;
template <typename T, bool unique, bool lookup = 0>
struct Compress {
    using ll = int64_t;
    vector<T> X{};
    vector<ll> counter{};
    bool frozen = false;
    Compress() {}
    template <typename U>
    Compress(const vector<U>& A) {
        extend(A);
    }
    void add(T x) {
        frozen = false;
        X.push_back(x);
    }
    template <typename U>
    void extend(const vector<U>& A) {
        frozen = false;
        for (const auto& x : A) {
            X.push_back(x);
        }
    }
    void build() {
        if (frozen) return;
        if (!std::is_sorted(X.begin(), X.end())) { std::sort(X.begin(), X.end()); }
        if constexpr (unique) { unique_inplace(X); }
        if constexpr (lookup) {
            if (!X.empty()) {
                auto min_ = X.front();
                auto max_ = X.back();
                counter.clear();
                counter.resize(max_ - min_ + 1, 0);
                for (const auto& x : X) {
                    counter[x - min_] += 1;
                }
                counter = cumsum(counter, 0LL);
            }
        } else {
            frozen = cumsum(counter, 0LL).empty();
        }
        frozen = true;
    }
    ll bisect_left(T x) const {
        assert(frozen);
        if (X.empty()) return 0;
        if (x <= X.front()) return 0;
        if (x > X.back()) return X.size();
        if constexpr (lookup) {
            return counter[x - X.front()];
        } else {
            return std::distance(X.begin(), std::lower_bound(X.begin(), X.end(), x));
        }
    }
    ll bisect_right(T x) const {
        assert(frozen);
        if (X.empty()) return 0;
        if (x < X.front()) return 0;
        if (x >= X.back()) return X.size();
        if constexpr (lookup) {
            return counter[x - X.front() + 1];
        } else {
            return std::distance(X.begin(), std::upper_bound(X.begin(), X.end(), x));
        }
    }
    template <bool inclusive = 0>
    ll bisect(T x) const {
        if constexpr (inclusive) {
            return bisect_right(x);
        } else {
            return bisect_left(x);
        }
    }
    bool contains(T x) const {
        assert(frozen);
        ll i = bisect_left(x);
        if (i == X.size()) return false;
        return X[i] == x;
    }
    ll size() const { return X.size(); }
    T operator[](int64_t idx) const { return X[idx]; }
};
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);
    }
    Compress<ll, 1> comp;
    for (auto [x, y, v] : XYV) {
        comp.add(y - (Q - 1));
        comp.add(y + 1);
    }
    comp.build();
    auto seg = LazySegTree<MMax<ll, INF>, MAdd<ll>, operate>(comp.size());
    seg.apply(0, comp.size(), INF);
    ll res = 0;
    for (auto t : T) {
        for (auto [x, y, v] : todo[t + (P - 1)]) {
            assert(0 <= y - (Q - 1));
            seg.apply(comp.bisect(y - (Q - 1)), comp.bisect(y + 1), v);
        }
        for (auto [x, y, v] : todo[t - 1]) {
            assert(0 <= y - (Q - 1));
            seg.apply(comp.bisect(y - (Q - 1)), comp.bisect(y + 1), -v);
        }
        ll nres = seg.fold_all();
        chmax(res, nres);
    }
    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);
}
yukicoder

結果

ソースコード
