#1178766 (C++23) No.2885 Range Triangle Collision Decision Queries

• 問題: No.2885 Range Triangle Collision Decision Queries
• ユーザー: Rac
• 提出日時: 2026-08-24 23:09:06
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 185 ms / 3,000 ms
• コード長: 3,162 bytes
• コンパイル時間: 2,187 ms
• コンパイル使用メモリ: 338,224 KB
• 実行使用メモリ: 46,780 KB
• 最終ジャッジ日時: 2026-08-24 23:09:37
• 合計ジャッジ時間: 18,576 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 53

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = (1LL << 62);

struct Node {
    ll mnX, mnY, mnB;
    ll mxXD, mxYD, mxZ;

    Node(
        ll mnX_ = INF,
        ll mnY_ = INF,
        ll mnB_ = INF,
        ll mxXD_ = -INF,
        ll mxYD_ = -INF,
        ll mxZ_ = -INF
    ) :
        mnX(mnX_), mnY(mnY_), mnB(mnB_),
        mxXD(mxXD_), mxYD(mxYD_), mxZ(mxZ_) {}
};

Node mergeNode(const Node& a, const Node& b) {
    Node res;
    res.mnX = min(a.mnX, b.mnX);
    res.mnY = min(a.mnY, b.mnY);
    res.mnB = min(a.mnB, b.mnB);

    res.mxXD = max(a.mxXD, b.mxXD);
    res.mxYD = max(a.mxYD, b.mxYD);
    res.mxZ = max(a.mxZ, b.mxZ);

    return res;
}

struct SegTree {
    int n;
    vector<Node> seg;

    SegTree(const vector<Node>& a) {
        int sz = (int)a.size();

        n = 1;
        while (n < sz) n <<= 1;

        seg.assign(2 * n, Node());

        for (int i = 0; i < sz; i++) {
            seg[n + i] = a[i];
        }

        for (int i = n - 1; i >= 1; i--) {
            seg[i] = mergeNode(seg[i << 1], seg[i << 1 | 1]);
        }
    }

    // [l, r) のクエリ
    Node query(int l, int r) const {
        Node left, right;

        l += n;
        r += n;

        while (l < r) {
            if (l & 1) {
                left = mergeNode(left, seg[l]);
                l++;
            }

            if (r & 1) {
                --r;
                right = mergeNode(seg[r], right);
            }

            l >>= 1;
            r >>= 1;
        }

        return mergeNode(left, right);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<ll> A(N), B(N), D(N);
    vector<ll> X(N), Y(N), Z(N);

    vector<Node> init(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i] >> D[i];

        X[i] = A[i] + B[i];
        Y[i] = B[i] - A[i];
        Z[i] = B[i] - D[i];

        init[i] = Node(
            X[i],                    // min X
            Y[i],                    // min Y
            B[i],                    // min B
            X[i] - 2 * D[i],         // max (X - 2D)
            Y[i] - 2 * D[i],         // max (Y - 2D)
            Z[i]                     // max Z
        );
    }

    SegTree seg(init);

    int Q;
    cin >> Q;

    while (Q--) {
        int S, L, R;
        cin >> S >> L >> R;

        --S;
        --L;
        // R は半開区間の右端としてそのまま使える

        Node t = seg.query(L, R);

        bool ok = true;

        // X_j > X_s - 2D_s
        if (t.mnX <= X[S] - 2 * D[S]) {
            ok = false;
        }

        // Y_j > Y_s - 2D_s
        if (t.mnY <= Y[S] - 2 * D[S]) {
            ok = false;
        }

        // B_j > B_s - D_s
        if (t.mnB <= Z[S]) {
            ok = false;
        }

        // X_j - 2D_j < X_s
        if (t.mxXD >= X[S]) {
            ok = false;
        }

        // Y_j - 2D_j < Y_s
        if (t.mxYD >= Y[S]) {
            ok = false;
        }

        // Z_j < B_s
        if (t.mxZ >= B[S]) {
            ok = false;
        }

        cout << (ok ? "Yes" : "No") << '\n';
    }

    return 0;
}