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

• 問題: No.2885 Range Triangle Collision Decision Queries
• ユーザー: Rac
• 提出日時: 2026-08-24 23:35:21
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 47 ms / 3,000 ms
• コード長: 8,474 bytes
• コンパイル時間: 2,617 ms
• コンパイル使用メモリ: 359,828 KB
• 実行使用メモリ: 34,776 KB
• 最終ジャッジ日時: 2026-08-24 23:35:46
• 合計ジャッジ時間: 17,776 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

static constexpr int MAXN = 200000;
static constexpr int MAXQ = 200000;
static constexpr int MAXLOG = 18;
static constexpr int MAXG = MAXN + MAXLOG + 8;

/*
    各三角形について

    U0 = A+B
    U1 = B-A
    U2 = B

    L0 = A+B-2D
    L1 = B-A-2D
    L2 = B-D

    を使う。

    区間で必要なのは
      min U0, min U1, min U2,
      max L0, max L1, max L2

    なので、max を min に統一するため

      { U0, U1, U2, -L0, -L1, -L2 }

    を保持する。
*/
struct Six {
    i64 v0, v1, v2;
    i64 v3, v4, v5;
};

static Six basev[MAXN];
static Six agg[MAXN];

struct RawQ {
    int s, l, r, id, g;
};

struct GQ {
    int s, l, r, id;
};

static RawQ rawq[MAXQ];
static GQ gq[MAXQ];

static unsigned char ans[MAXQ];

static int off[MAXLOG + 1];

static int cnt[MAXG];
static int st[MAXG + 1];
static int pos[MAXG];

static int minL[MAXG];
static int maxR[MAXG];

static inline __attribute__((always_inline))
void take_min(Six& a, const Six& b) {
    if (b.v0 < a.v0) a.v0 = b.v0;
    if (b.v1 < a.v1) a.v1 = b.v1;
    if (b.v2 < a.v2) a.v2 = b.v2;
    if (b.v3 < a.v3) a.v3 = b.v3;
    if (b.v4 < a.v4) a.v4 = b.v4;
    if (b.v5 < a.v5) a.v5 = b.v5;
}

// [l,l] の1要素だけの場合
static inline __attribute__((always_inline))
bool check_one(const Six& x, const Six& s) {
    return
        x.v0 > -s.v3 &&
        x.v1 > -s.v4 &&
        x.v2 > -s.v5 &&

        x.v3 > -s.v0 &&
        x.v4 > -s.v1 &&
        x.v5 > -s.v2;
}

// range aggregate = min(x,y)
// min(x_i,y_i) > t
// ⇔ x_i > t && y_i > t
//
// なので実際に min を作る必要すらない。
static inline __attribute__((always_inline))
bool check_two(
    const Six& x,
    const Six& y,
    const Six& s
) {
    return
        x.v0 > -s.v3 && y.v0 > -s.v3 &&
        x.v1 > -s.v4 && y.v1 > -s.v4 &&
        x.v2 > -s.v5 && y.v2 > -s.v5 &&

        x.v3 > -s.v0 && y.v3 > -s.v0 &&
        x.v4 > -s.v1 && y.v4 > -s.v1 &&
        x.v5 > -s.v2 && y.v5 > -s.v2;
}

class FastInput {
    static constexpr int SZ = 1 << 20;

    char buf[SZ];
    int ptr = 0;
    int len = 0;

    inline char gc() {
        if (ptr == len) {
            len = (int)fread(buf, 1, SZ, stdin);
            ptr = 0;

            if (!len)
                return 0;
        }

        return buf[ptr++];
    }

public:
    inline i64 readLL() {
        char c = gc();

        while (c <= ' ')
            c = gc();

        bool neg = false;

        if (c == '-') {
            neg = true;
            c = gc();
        }

        i64 x = 0;

        while (c >= '0') {
            x = x * 10 + (c - '0');
            c = gc();
        }

        return neg ? -x : x;
    }

    inline int readInt() {
        return (int)readLL();
    }
};

int main() {
    FastInput in;

    const int N = in.readInt();

    for (int i = 0; i < N; ++i) {
        const i64 A = in.readLL();
        const i64 B = in.readLL();
        const i64 D = in.readLL();

        const i64 U0 = A + B;
        const i64 U1 = B - A;
        const i64 U2 = B;

        const i64 L0 = U0 - 2 * D;
        const i64 L1 = U1 - 2 * D;
        const i64 L2 = B - D;

        basev[i] = {
            U0,
            U1,
            U2,
            -L0,
            -L1,
            -L2
        };
    }

    /*
        l != r のクエリについて

        k = msb(l xor r)

        とすると、長さ 2^(k+1) の同一ブロック内で

                    mid
        -----------|-----------
             l                 r

        と必ず左右に分かれる。

        左側は suffix minimum、
        右側は prefix minimum

        だけ作ればよい。
    */

    int levels = 0;
    int G = 0;

    while ((1 << levels) < N) {
        off[levels] = G;

        const int blockSize = 1 << (levels + 1);

        G += (N + blockSize - 1) / blockSize;

        ++levels;
    }

    for (int g = 0; g < G; ++g) {
        minL[g] = N;
        maxR[g] = -1;
    }

    const int Q = in.readInt();

    // l != r のクエリ数
    int M = 0;

    for (int id = 0; id < Q; ++id) {
        const int s = in.readInt() - 1;
        const int l = in.readInt() - 1;
        const int r = in.readInt() - 1;

        /*
            長さ1ならRMQを作る必要がない。
        */
        if (l == r) {
            ans[id] =
                (unsigned char)check_one(
                    basev[l],
                    basev[s]
                );

            continue;
        }

        const unsigned z = (unsigned)(l ^ r);

        const int k =
            31 - __builtin_clz(z);

        /*
            2^(k+1) ブロックの番号
        */
        const int b =
            l >> (k + 1);

        const int g =
            off[k] + b;

        rawq[M++] = {
            s, l, r, id, g
        };

        ++cnt[g];

        if (l < minL[g])
            minL[g] = l;

        if (r > maxR[g])
            maxR[g] = r;
    }

    /*
        group ID による counting sort。

        linked list にすると、
        Query 配列をランダムに辿ることになる。

        ここでは同じ group の Query を
        gq[] の連続領域に詰める。
    */

    for (int g = 0; g < G; ++g) {
        st[g + 1] =
            st[g] + cnt[g];
    }

    memcpy(
        pos,
        st,
        G * sizeof(int)
    );

    for (int i = 0; i < M; ++i) {
        const RawQ& q = rawq[i];

        gq[pos[q.g]++] = {
            q.s,
            q.l,
            q.r,
            q.id
        };
    }

    /*
        各 Disjoint Sparse Table level を処理。

        ただし Sparse Table 全体は作らない。

        その group に属する Query の

            最小 l ～ mid
            mid ～ 最大 r

        の部分だけ構築する。
    */
    for (int k = 0; k < levels; ++k) {
        const int half =
            1 << k;

        const int blockSize =
            half << 1;

        const int groupCount =
            (N + blockSize - 1)
            / blockSize;

        const int groupOffset =
            off[k];

        for (
            int b = 0;
            b < groupCount;
            ++b
        ) {
            const int g =
                groupOffset + b;

            if (cnt[g] == 0)
                continue;

            const int mid =
                b * blockSize
                + half;

            const int lo =
                minL[g];

            const int hi =
                maxR[g];

            /*
                [lo, mid) の
                suffix componentwise-min
            */
            Six cur =
                basev[mid - 1];

            agg[mid - 1] = cur;

            for (
                int i = mid - 2;
                i >= lo;
                --i
            ) {
                take_min(
                    cur,
                    basev[i]
                );

                agg[i] = cur;
            }

            /*
                [mid, hi] の
                prefix componentwise-min
            */
            cur = basev[mid];

            agg[mid] = cur;

            for (
                int i = mid + 1;
                i <= hi;
                ++i
            ) {
                take_min(
                    cur,
                    basev[i]
                );

                agg[i] = cur;
            }

            /*
                group 内の Query は
                counting sort 済みなので連続。
            */
            const int end =
                st[g + 1];

            for (
                int p = st[g];
                p < end;
                ++p
            ) {
                const GQ& q =
                    gq[p];

                ans[q.id] =
                    (unsigned char)
                    check_two(
                        agg[q.l],
                        agg[q.r],
                        basev[q.s]
                    );
            }
        }
    }

    /*
        出力
    */
    static char out[MAXQ * 4 + 8];

    char* p = out;

    for (int i = 0; i < Q; ++i) {
        if (ans[i]) {
            *p++ = 'Y';
            *p++ = 'e';
            *p++ = 's';
            *p++ = '\n';
        } else {
            *p++ = 'N';
            *p++ = 'o';
            *p++ = '\n';
        }
    }

    fwrite(
        out,
        1,
        (size_t)(p - out),
        stdout
    );

    return 0;
}