結果

問題 No.2885 Range Triangle Collision Decision Queries
ユーザー Rac
提出日時 2025-04-17 17:05:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,158 bytes
コンパイル時間 3,920 ms
コンパイル使用メモリ 291,840 KB
実行使用メモリ 249,692 KB
最終ジャッジ日時 2025-04-17 17:07:22
合計ジャッジ時間 105,216 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// --- セグ木 for max / min over E_i, F_i ---
template<class T, class Op>
struct SegTree {
    int n;
    vector<T> st;
    Op op; T e;
    SegTree(int _n, T _e, Op _op):n(_n),e(_e),op(_op){
        st.assign(4*n, e);
    }
    void build(int p,int l,int r,const vector<T>&A){
        if(l==r){ st[p]=A[l]; return; }
        int m=(l+r)>>1;
        build(p<<1,l,m,A); build(p<<1|1,m+1,r,A);
        st[p]=op(st[p<<1],st[p<<1|1]);
    }
    T query(int p,int l,int r,int i,int j){
        if(i>r||j<l) return e;
        if(i<=l&&r<=j) return st[p];
        int m=(l+r)>>1;
        return op(query(p<<1,l,m,i,j), query(p<<1|1,m+1,r,i,j));
    }
    // wrapper
    void build(const vector<T>&A){ build(1,0,n-1,A); }
    T query(int l,int r){ return query(1,0,n-1,l,r); }
};

// --- Merge‑sort tree: q→min p  ---
struct Merge_qp {
    int n;
    vector<vector<ll>> Q;      // 各ノードの q_k の昇順リスト
    vector<vector<ll>> prefP;  // 同長さで，prefix-min of p_k
    Merge_qp(int _n):n(_n){
        Q.resize(4*n);
        prefP.resize(4*n);
    }
    void build(int p,int l,int r,
               const vector<ll>& q, const vector<ll>& pval){
        if(l==r){
            Q[p]={q[l]};
            prefP[p]={pval[l]};
            return;
        }
        int m=(l+r)>>1;
        build(p<<1,l,m,q,pval);
        build(p<<1|1,m+1,r,q,pval);
        // マージ
        auto &Lq=Q[p<<1], &Rq=Q[p<<1|1];
        auto &Lp=prefP[p<<1], &Rp=prefP[p<<1|1];
        int sz=Lq.size()+Rq.size();
        Q[p].resize(sz);
        prefP[p].resize(sz);
        merge(Lq.begin(),Lq.end(),Rq.begin(),Rq.end(),Q[p].begin());
        // prefix-min を作るために，対応する p_k も併せてマージしつつ min を取る
        int i=0,j=0,k=0;
        ll curMin = INF;
        while(i<(int)Lq.size()||j<(int)Rq.size()){
            if(j==(int)Rq.size() || (i<(int)Lq.size() && Lq[i] <= Rq[j])){
                curMin = min(curMin, Lp[i]);
                ++i;
            } else {
                curMin = min(curMin, Rp[j]);
                ++j;
            }
            prefP[p][k++] = curMin;
        }
    }
    // 区間 [ql, qr] で q_k < qS の最小 p を返す
    ll query_sub(int p,int l,int r,int i,int j,ll qS){
        if(i>r||j<l) return INF;
        if(i<=l&&r<=j){
            // このノード内で q_k<qS の最小 prefix を二分探索
            int pos = lower_bound(Q[p].begin(), Q[p].end(), qS) - Q[p].begin();
            if(pos==0) return INF; 
            return prefP[p][pos-1];
        }
        int m=(l+r)>>1;
        return min(
          query_sub(p<<1,l,m,i,j,qS),
          query_sub(p<<1|1,m+1,r,i,j,qS)
        );
    }
    ll query(int L,int R,ll qS){
        return query_sub(1,0,n-1,L,R,qS);
    }
};

// --- Merge‑sort tree: p→max q  ---
struct Merge_pq {
    int n;
    vector<vector<ll>> P;       // 各ノードの p_k の昇順リスト
    vector<vector<ll>> suffQ;   // suffix-max of q_k
    Merge_pq(int _n):n(_n){
        P.resize(4*n);
        suffQ.resize(4*n);
    }
    void build(int p,int l,int r,
               const vector<ll>& pval, const vector<ll>& q){
        if(l==r){
            P[p]={pval[l]};
            suffQ[p]={q[l]};
            return;
        }
        int m=(l+r)>>1;
        build(p<<1,l,m,pval,q);
        build(p<<1|1,m+1,r,pval,q);
        auto &Lp=P[p<<1], &Rp=P[p<<1|1];
        auto &Lq=suffQ[p<<1], &Rq=suffQ[p<<1|1];
        int sz=Lp.size()+Rp.size();
        P[p].resize(sz);
        suffQ[p].resize(sz);
        merge(Lp.begin(),Lp.end(),Rp.begin(),Rp.end(),P[p].begin());
        // suffix-max をつくるため、マージ後に後ろから scan
        // まず対応 q_k を合わせるため同様にマージ二度
        vector<ll> allQ(sz);
        int i=0,j=0,k=0;
        while(i<(int)Lp.size()||j<(int)Rp.size()){
            if(j==(int)Rp.size() ||
               (i<(int)Lp.size() && Lp[i]<=Rp[j])){
                allQ[k++] = Lq[i++];
            } else {
                allQ[k++] = Rq[j++];
            }
        }
        ll curMax = -INF;
        for(int t=sz-1;t>=0;--t){
            curMax = max(curMax, allQ[t]);
            suffQ[p][t] = curMax;
        }
    }
    // 区間 [L,R] で p_k > pS の最大 q を返す
    ll query_sub(int p,int l,int r,int i,int j,ll pS){
        if(i>r||j<l) return -INF;
        if(i<=l&&r<=j){
            int pos = upper_bound(P[p].begin(), P[p].end(), pS)
                    - P[p].begin();
            if(pos==(int)P[p].size()) return -INF;
            return suffQ[p][pos];
        }
        int m=(l+r)>>1;
        return max(
          query_sub(p<<1,l,m,i,j,pS),
          query_sub(p<<1|1,m+1,r,i,j,pS)
        );
    }
    ll query(int L,int R,ll pS){
        return query_sub(1,0,n-1,L,R,pS);
    }
};


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

    int N; cin>>N;
    vector<ll>A(N),B(N),D(N),E(N),F(N),p(N),q(N);
    for(int i=0;i<N;i++){
        cin>>A[i]>>B[i]>>D[i];
        E[i]=B[i]-D[i];
        F[i]=B[i];
        p[i]=A[i]+B[i];
        q[i]=A[i]-B[i];
    }

    // 1) build ST1,ST2
    SegTree<ll,function<ll(ll,ll)>> stE(N, -INF,
        [](ll a,ll b){return max(a,b);} );
    SegTree<ll,function<ll(ll,ll)>> stF(N, +INF,
        [](ll a,ll b){return min(a,b);} );
    stE.build(E);
    stF.build(F);

    // 2) build merge‑sort trees
    Merge_qp  ms_qp(N);
    ms_qp.build(1,0,N-1,q,p);
    Merge_pq  ms_pq(N);
    ms_pq.build(1,0,N-1,p,q);

    int Q; cin>>Q;
    while(Q--){
        int S,L,R;
        cin>>S>>L>>R;
        --S; --L; --R;
        ll AS=A[S], BS=B[S], DS=D[S];
        ll pS=p[S], qS=q[S];

        // V1,V2
        bool ok1 = (stE.query(L,R) < BS);
        bool ok2 = (stF.query(L,R) > BS - DS);

        // H1: q_k < qS の範囲 min p_k
        ll m1 = ms_qp.query(L,R, qS);
        bool ok3 = (m1 > pS - 2*DS);

        // H2: p_k > pS の範囲 max q_k
        ll m2 = ms_pq.query(L,R, pS);
        bool ok4 = (m2 < qS + 2*DS);

        cout << ((ok1&&ok2&&ok3&&ok4) ? "Yes\n" : "No\n");
    }
    return 0;
}
0