結果

問題 No.2885 Range Triangle Collision Decision Queries
ユーザー karinohito
提出日時 2024-09-08 14:54:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,320 ms / 3,000 ms
コード長 1,378 bytes
コンパイル時間 6,317 ms
コンパイル使用メモリ 202,336 KB
最終ジャッジ日時 2025-02-24 05:43:05
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include<atcoder/segtree>
using namespace atcoder;
using ll=long long;
ll opmax(ll a,ll b){return max(a,b);}
ll emax(){return -1e18;}

ll opmin(ll a,ll b){return min(a,b);}
ll emin(){return 1e18;}

int main() {
    
    ll N;
    cin>>N;
    segtree<ll,opmax,emax> segH(N),segL(N),segR(N);
    segtree<ll,opmin,emin> segl(N),segr(N),segh(N);
    vector<ll> A(N),B(N),D(N);
    for(int i=0;i<N;i++){
        cin>>A[i]>>B[i]>>D[i];
        segH.set(i,B[i]-D[i]);
        segl.set(i,B[i]-A[i]);
        segr.set(i,B[i]+A[i]);

        segh.set(i,B[i]);
        segL.set(i,B[i]-A[i]-2*D[i]);
        segR.set(i,B[i]+A[i]-2*D[i]);
    }
    ll Q;
    cin>>Q;
    for(int q=0;q<Q;q++){
        ll S,Lq,Rq;
        cin>>S>>Lq>>Rq;
        S--;Lq--;
        ll h=segh.prod(Lq,Rq);
        ll l=segl.prod(Lq,Rq);
        ll r=segr.prod(Lq,Rq);

        ll H=segH.prod(Lq,Rq);
        ll L=segL.prod(Lq,Rq);
        ll R=segR.prod(Lq,Rq);
        // cout<<h<<" "<<H<<" "<<l<<" "<<L<<" "<<r<<" "<<R<<endl;
        // cout<<B[S]<<" "<<B[S]-D[S]<<" "<<B[S]-A[S]<<" "<<B[S]-A[S]-2*D[S]<<" "<<B[S]+A[S]<<" "<<B[S]+A[S]-2*D[S]<<endl;
        
        bool OK=1;
        if(h<=B[S]-D[S]||H>=B[S])OK=0;
        if(l<=B[S]-A[S]-2*D[S]||L>=B[S]-A[S])OK=0;
        if(r<=B[S]+A[S]-2*D[S]||R>=B[S]+A[S])OK=0;
        cout<<(OK?"Yes":"No")<<endl;
    }
}
0