結果
問題 |
No.2885 Range Triangle Collision Decision Queries
|
ユーザー |
|
提出日時 | 2024-09-07 20:35:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 274 ms / 3,000 ms |
コード長 | 3,054 bytes |
コンパイル時間 | 6,336 ms |
コンパイル使用メモリ | 336,692 KB |
実行使用メモリ | 39,704 KB |
最終ジャッジ日時 | 2024-09-07 20:36:04 |
合計ジャッジ時間 | 24,951 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; // https://judge.yosupo.jp/submission/217135 using idt=std::size_t; template<class _Tp> struct _Sprod{ _Tp*f; idt n; _Sprod():f(nullptr),n(0){} void build(idt _n,auto&&fn){ delete []f; f=new _Tp[(_n<2?1:(std::__lg(_n-1)+1))*_n]; n=_n; for(idt i=0;i<n;++i){ f[i]=fn(i); } for(idt j=2,w=1;j<n;j<<=1,++w){ auto t=f+w*n; for(idt i=0;i+j<n;i+=2*j){ t[i+j-1]=f[i+j-1],t[i+j]=f[i+j]; for(idt k=i+j-1;k>i;--k){ t[k-1]=f[k-1]*t[k]; } idt ed=std::min(n,i+j+j)-1; for(idt k=i+j;k<ed;++k){ t[k+1]=t[k]*f[k+1]; } } } } ~_Sprod(){ delete []f; } _Tp get(idt l,idt r)const{ if(l==r){ return f[l]; } auto t=f+(63^__builtin_clzll(l^r))*n; return t[l]*t[r]; } }; template<class _Tp,idt _Bk=16> struct RangeProd{ _Tp*arr,*pre,*suf; idt n; _Sprod<_Tp> spd; RangeProd(idt _n,auto&&fn):arr(new _Tp[_n]),pre(new _Tp[_n]),suf(new _Tp[_n]),n(_n){ for(idt i=0;i<n;++i){ arr[i]=fn(i); } for(idt i=0;i<n;i+=_Bk){ pre[i]=arr[i]; for(idt j=i+1,ed=std::min(n,i+_Bk);j<ed;++j){ pre[j]=pre[j-1]*arr[j]; } } for(idt i=0;i<n;i+=_Bk){ idt ed=std::min(n,i+_Bk); suf[ed-1]=arr[ed-1]; for(idt j=ed-1;j!=i;--j){ suf[j-1]=arr[j-1]*suf[j]; } } if(n>_Bk){ spd.build(n/_Bk,[&](idt i){ return suf[i*_Bk]; }); } } ~RangeProd(){ delete []arr; delete []pre; delete []suf; } _Tp get(idt l,idt r)const{ idt bl=l/_Bk,br=r/_Bk; if(bl==br){ _Tp res=arr[l]; for(idt i=l+1;i<=r;++i){ res=res*arr[i]; } return res; } if(bl+1==br){ return suf[l]*pre[r]; } return suf[l]*spd.get(bl+1,br-1)*pre[r]; } }; struct Data { long long l1, l2, l3, r1, r2, r3; Data operator*(Data b) const { return { max(l1, b.l1), max(l2, b.l2), max(l3, b.l3), min(r1, b.r1), min(r2, b.r2), min(r3, b.r3) }; } }; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; RangeProd<Data> st(N, [](idt i) -> Data { long long A, B, D; cin >> A >> B >> D; return { B - D, (A - D) + (B - D), A - B, B, A + B, (A + D) - (B - D) }; }); int Q; cin >> Q; for (int i = 0; i != Q; ++i) { int S, L, R; cin >> S >> L >> R; auto [l1, l2, l3, r1, r2, r3] = st.arr[S - 1]; auto [sl1, sl2, sl3, sr1, sr2, sr3] = st.get(L - 1, R - 1); cout << (l1 < sr1 && sl1 < r1 && l2 < sr2 && sl2 < r2 && l3 < sr3 && sl3 < r3 ? "Yes\n" : "No\n"); } }