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

• 問題: No.2885 Range Triangle Collision Decision Queries
• ユーザー: Rac
• 提出日時: 2026-08-24 23:19:05
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 72 ms / 3,000 ms
• コード長: 4,300 bytes
• コンパイル時間: 2,235 ms
• コンパイル使用メモリ: 337,636 KB
• 実行使用メモリ: 25,088 KB
• 最終ジャッジ日時: 2026-08-24 23:19:26
• 合計ジャッジ時間: 14,584 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

using ll = long long;

static constexpr int MAXN = 200016;
static constexpr int MAXQ = 200005;

// v[0..2] : U
// v[3..5] : L
alignas(64) static ll v[6][MAXN];

// それぞれの単調スタック用 Union-Find
alignas(64) static int parent_[6][MAXN];
alignas(64) static int stk[6][MAXN];

struct Query {
    int s;
    int l;
    int next;
};

static Query qs[MAXQ];
static int head[MAXN];
static unsigned char ans[MAXQ];

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

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

    inline char getChar() {
        if (ptr == len) {
            len = (int)fread(buf, 1, SZ, stdin);
            ptr = 0;
            if (len == 0) return 0;
        }
        return buf[ptr++];
    }

public:
    inline ll nextLong() {
        char c = getChar();

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

        bool neg = false;
        if (c == '-') {
            neg = true;
            c = getChar();
        }

        ll x = 0;
        while ('0' <= c && c <= '9') {
            x = x * 10 + (c - '0');
            c = getChar();
        }

        return neg ? -x : x;
    }

    inline int nextInt() {
        return (int)nextLong();
    }
};

template<int K>
inline int findRoot(int x) {
    // path halving
    while (parent_[K][x] != x) {
        parent_[K][x] =
            parent_[K][parent_[K][x]];
        x = parent_[K][x];
    }
    return x;
}

template<int K>
inline void addMin(int i, int& top) {
    parent_[K][i] = i;

    const ll x = v[K][i];

    while (top &&
           v[K][stk[K][top - 1]] > x) {
        const int p = stk[K][--top];
        parent_[K][p] = i;
    }

    stk[K][top++] = i;
}

template<int K>
inline void addMax(int i, int& top) {
    parent_[K][i] = i;

    const ll x = v[K][i];

    while (top &&
           v[K][stk[K][top - 1]] < x) {
        const int p = stk[K][--top];
        parent_[K][p] = i;
    }

    stk[K][top++] = i;
}

int main() {
    FastScanner fs;

    const int N = fs.nextInt();

    for (int i = 0; i < N; ++i) {
        const ll A = fs.nextLong();
        const ll B = fs.nextLong();
        const ll D = fs.nextLong();

        const ll u0 = A + B;
        const ll u1 = B - A;
        const ll u2 = B;

        v[0][i] = u0;
        v[1][i] = u1;
        v[2][i] = u2;

        v[3][i] = u0 - 2 * D;
        v[4][i] = u1 - 2 * D;
        v[5][i] = u2 - D;
    }

    fill(head, head + N, -1);

    const int Q = fs.nextInt();

    for (int q = 0; q < Q; ++q) {
        const int s = fs.nextInt() - 1;
        const int l = fs.nextInt() - 1;
        const int r = fs.nextInt() - 1;

        qs[q].s = s;
        qs[q].l = l;

        // 右端 r の linked list に追加
        qs[q].next = head[r];
        head[r] = q;
    }

    int top0 = 0;
    int top1 = 0;
    int top2 = 0;
    int top3 = 0;
    int top4 = 0;
    int top5 = 0;

    for (int r = 0; r < N; ++r) {
        // U 側は区間 minimum
        addMin<0>(r, top0);
        addMin<1>(r, top1);
        addMin<2>(r, top2);

        // L 側は区間 maximum
        addMax<3>(r, top3);
        addMax<4>(r, top4);
        addMax<5>(r, top5);

        // 右端が r の全クエリを処理
        for (int qi = head[r];
             qi != -1;
             qi = qs[qi].next) {

            const int s = qs[qi].s;
            const int l = qs[qi].l;

            // short-circuit するので、
            // No になりやすいケースでは6回全部 find しない。
            const bool ok =
                v[0][findRoot<0>(l)] > v[3][s] &&
                v[3][findRoot<3>(l)] < v[0][s] &&

                v[1][findRoot<1>(l)] > v[4][s] &&
                v[4][findRoot<4>(l)] < v[1][s] &&

                v[2][findRoot<2>(l)] > v[5][s] &&
                v[5][findRoot<5>(l)] < v[2][s];

            ans[qi] = (unsigned char)ok;
        }
    }

    // 出力もまとめて fwrite
    static char out[MAXQ * 4 + 16];
    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, p - out, stdout);

    return 0;
}