結果

問題 No.2885 Range Triangle Collision Decision Queries
コンテスト
ユーザー Rac
提出日時 2026-08-24 23:03:14
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,015 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,722 ms
コンパイル使用メモリ 339,148 KB
実行使用メモリ 30,848 KB
最終ジャッジ日時 2026-08-24 23:04:04
合計ジャッジ時間 33,828 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 18 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 INF64 = (1LL<<62);

struct Node {
    int64 mn[4];
    Node() { mn[0]=mn[1]=mn[2]=mn[3]=INF64; }
    void set(int idx, int64 v){ mn[idx]=v; }
    static Node merge(const Node& a, const Node& b){
        Node c;
        for(int i=0;i<4;i++) c.mn[i]=min(a.mn[i], b.mn[i]);
        return c;
    }
};

struct SegTree {
    int n;
    vector<Node> st;
    SegTree(const vector<array<int64,4>>& base){
        int sz = base.size();
        n = 1; while(n<sz) n <<= 1;
        st.assign(2*n, Node());
        for(int i=0;i<sz;i++){
            for(int t=0;t<4;t++) st[n+i].mn[t] = base[i][t];
        }
        for(int i=n-1;i>=1;i--){
            st[i] = Node::merge(st[i<<1], st[i<<1|1]);
        }
    }
    // query on [l,r)  0-indexed
    Node query(int l, int r) const{
        Node L, R;
        for(l+=n, r+=n; l<r; l>>=1, r>>=1){
            if (l&1) L = Node::merge(L, st[l++]);
            if (r&1) R = Node::merge(st[--r], R);
        }
        return Node::merge(L, R);
    }
};

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

    int N;
    if(!(cin>>N)) return 0;
    vector<int64> A(N), B(N), D(N);
    for(int i=0;i<N;i++) cin>>A[i]>>B[i]>>D[i];

    // pre-compute U_{tk} = ±A ± B + D
    vector<array<int64,4>> base(N);
    for(int i=0;i<N;i++){
        base[i][0] =  A[i] + B[i] + D[i];
        base[i][1] =  A[i] - B[i] + D[i];
        base[i][2] = -A[i] + B[i] + D[i];
        base[i][3] = -A[i] - B[i] + D[i];
    }
    SegTree seg(base);

    int Q; cin>>Q;
    while(Q--){
        int S,L,R; cin>>S>>L>>R;
        --S; --L; --R;   // 0-index
        Node nd = seg.query(L, R+1);

        int64 T[4] = {
            A[S] + B[S],
            A[S] - B[S],
            -A[S] + B[S],
            -A[S] - B[S]
        };
        int64 F = -INF64;
        for(int t=0;t<4;t++){
            F = max(F, T[t] - nd.mn[t]);
        }
        cout << (F < D[S] ? "Yes\n" : "No\n");
    }
    return 0;
}
0