#682638 (C++17) No.1625 三角形の質問

• 問題: No.1625 三角形の質問
• ユーザー: KoD
• 提出日時: 2021-07-23 21:48:00
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,773 ms / 6,000 ms
• コード長: 7,841 bytes
• コンパイル時間: 2,510 ms
• コンパイル使用メモリ: 221,312 KB
• 最終ジャッジ日時: 2025-01-23 07:57:33
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 1
other	AC * 19

ソースコード

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div;

class revrep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { --itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr revrep(const usize first, const usize last) noexcept
        : first(last - 1), last(std::min(first, last) - 1) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr u64 ceil_log2(const u64 x) {
    u64 e = 0;
    while (((u64)1 << e) < x) ++e;
    return e;
}

template <class Monoid> class SegmentTree {
    using M = Monoid;
    usize internal_size, seg_size;
    std::vector<M> data;

    void fetch(const usize k) { data[k] = data[2 * k] + data[2 * k + 1]; }

  public:
    explicit SegmentTree(const usize size = 0, const M& value = M::zero()) : SegmentTree(std::vector<M>(size, value)) {}
    explicit SegmentTree(const std::vector<M>& vec) : internal_size(vec.size()) {
        seg_size = 1 << ceil_log2(internal_size);
        data = std::vector<M>(2 * seg_size, M::zero());
        for (const usize i : rep(0, internal_size)) data[seg_size + i] = vec[i];
        for (const usize i : revrep(1, seg_size)) fetch(i);
    }

    usize size() const { return internal_size; }

    void assign(usize i, const M& value) {
        assert(i < internal_size);
        i += seg_size;
        data[i] = value;
        while (i > 1) {
            i >>= 1;
            fetch(i);
        }
    }

    M fold() const { return data[1]; }
    M fold(usize l, usize r) const {
        assert(l <= r and r <= internal_size);
        l += seg_size;
        r += seg_size;
        M ret_l = M::zero(), ret_r = M::zero();
        while (l < r) {
            if (l & 1) ret_l = ret_l + data[l++];
            if (r & 1) ret_r = data[--r] + ret_r;
            l >>= 1;
            r >>= 1;
        }
        return ret_l + ret_r;
    }

    template <class F> usize max_right(usize l, const F& f) const {
        assert(l <= internal_size);
        assert(f(M::zero()));
        if (l == internal_size) return internal_size;
        l += seg_size;
        M sum = M::zero();
        do {
            while (!(l & 1)) l >>= 1;
            if (!f(sum + data[l])) {
                while (l < seg_size) {
                    l = 2 * l;
                    if (f(sum + data[l])) sum = sum + data[l++];
                }
                return l - seg_size;
            }
            sum = sum + data[l++];
        } while ((l & -l) != l);
        return internal_size;
    }

    template <class F> usize min_left(usize r, const F& f) const {
        assert(r <= internal_size);
        assert(f(M::zero()));
        if (r == 0) return 0;
        r += seg_size;
        M sum = M::zero();
        do {
            r -= 1;
            while (r > 1 and (r & 1)) r >>= 1;
            if (!f(data[r] + sum)) {
                while (r < seg_size) {
                    r = 2 * r + 1;
                    if (f(data[r] + sum)) sum = data[r--] + sum;
                }
                return r + 1 - seg_size;
            }
            sum = data[r] + sum;
        } while ((r & -r) != r);
        return 0;
    }
};

template <class T> using Vec = std::vector<T>;

struct Max {
    i64 max;
    static Max zero() { return Max{-INFTY<i64>}; }
    Max operator+(const Max& other) const { return Max{std::max(max, other.max)}; }
};

std::array<i64, 3> get_triangle() {
    std::array<std::array<i64, 2>, 3> arr;
    for (auto& v : arr) {
        for (auto& x : v) {
            std::cin >> x;
        }
    }
    std::sort(arr.begin(), arr.end());
    std::array<i64, 3> ret;
    ret[0] = arr[0][0];
    ret[1] = arr[2][0];
    ret[2] =
        std::abs((arr[1][0] - arr[0][0]) * (arr[2][1] - arr[0][1]) - (arr[1][1] - arr[0][1]) * (arr[2][0] - arr[0][0]));
    return ret;
}

void main_() {
    usize N, Q;
    std::cin >> N >> Q;
    Vec<std::array<i64, 3>> pts(N);
    for (auto& arr : pts) {
        arr = get_triangle();
    }
    Vec<std::pair<usize, bool>> query(N + Q);
    for (const auto i : rep(0, N)) {
        query[i] = std::make_pair(i, false);
    }
    Vec<std::array<i64, 2>> range;
    for (const auto i : rep(0, Q)) {
        usize t;
        std::cin >> t;
        if (t == 1) {
            query[N + i] = std::make_pair(pts.size(), false);
            pts.emplace_back() = get_triangle();
        } else {
            query[N + i] = std::make_pair(range.size(), true);
            auto& [l, r] = range.emplace_back();
            std::cin >> l >> r;
        }
    }
    Vec<i64> xs;
    xs.reserve(pts.size());
    for (const auto& arr : pts) {
        xs.push_back(arr[0]);
    }
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    const auto Xlen = xs.size();
    Vec<Vec<i64>> ys(2 * Xlen);
    for (const auto& arr : pts) {
        usize x = Xlen + std::lower_bound(xs.begin(), xs.end(), arr[0]) - xs.begin();
        while (x > 0) {
            ys[x].push_back(arr[1]);
            x >>= 1;
        }
    }
    for (auto& vec : ys) {
        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }
    Vec<SegmentTree<Max>> seg(2 * Xlen);
    for (const auto i : rep(1, 2 * Xlen)) {
        seg[i] = SegmentTree<Max>(ys[i].size());
    }
    for (const auto& [i, f] : query) {
        if (f) {
            const auto& [l, r] = range[i];
            usize xl = Xlen + std::lower_bound(xs.begin(), xs.end(), l) - xs.begin();
            usize xr = 2 * Xlen;
            i64 ans = -1;
            while (xl < xr) {
                if (xl & 1) {
                    ans = std::max(
                        ans, seg[xl].fold(0, std::upper_bound(ys[xl].begin(), ys[xl].end(), r) - ys[xl].begin()).max);
                    xl += 1;
                }
                if (xr & 1) {
                    xr -= 1;
                    ans = std::max(
                        ans, seg[xr].fold(0, std::upper_bound(ys[xr].begin(), ys[xr].end(), r) - ys[xr].begin()).max);
                }
                xl >>= 1;
                xr >>= 1;
            }
            std::cout << ans << '\n';
        } else {
            const auto& arr = pts[i];
            usize x = Xlen + std::lower_bound(xs.begin(), xs.end(), arr[0]) - xs.begin();
            while (x > 0) {
                const usize y = std::lower_bound(ys[x].begin(), ys[x].end(), arr[1]) - ys[x].begin();
                seg[x].assign(y, Max{std::max(seg[x].fold(y, y + 1).max, arr[2])});
                x >>= 1;
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    main_();
    return 0;
}