結果
問題 |
No.2885 Range Triangle Collision Decision Queries
|
ユーザー |
![]() |
提出日時 | 2024-08-30 00:00:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,116 ms / 3,000 ms |
コード長 | 1,671 bytes |
コンパイル時間 | 3,705 ms |
コンパイル使用メモリ | 255,688 KB |
実行使用メモリ | 21,788 KB |
最終ジャッジ日時 | 2024-09-07 19:41:57 |
合計ジャッジ時間 | 58,417 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
コンパイルメッセージ
main.cpp: In function 'std::pair<long long int, long long int> convert(ll, ll, ll, int)': main.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type] 21 | } | ^
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/segtree> using namespace atcoder; using ll = long long; pair<ll, ll> convert(ll a, ll b, ll d, int type) { if (type == 0) { //__が分離直線, |が分離軸 return {b-d, b}; } if (type == 1) { // /が分離直線, \が分離軸 return {a-b, a-b+2*d}; } if (type == 2) { // \が分離直線, /が分離軸 return {a+b-2*d, a+b}; } } const ll INF = 8e18; ll opmin(ll a, ll b) {return min(a, b);} ll emin() {return INF;} ll opmax(ll a, ll b) {return max(a, b);} ll emax() {return -INF;} int main() { //入力 int N; cin >> N; vector<ll> A(N), B(N), D(N); for (int i = 0; i < N; i++) { cin >> A[i] >> B[i] >> D[i]; } int Q; cin >> Q; vector<int> S(Q), L(Q), R(Q); for (int i = 0; i < Q; i++) { cin >> S[i] >> L[i] >> R[i]; } //答え vector<bool> ans(Q, true); //各分離直線の向きについて調べる for (int k = 0; k < 3; k++) { vector<ll> p(N), q(N); //投影する for (int i = 0; i < N; i++) { auto[tp, tq] = convert(A[i], B[i], D[i], k); p[i] = tp; q[i] = tq; } segtree<ll, opmax, emax> pseg(p); segtree<ll, opmin, emin> qseg(q); for (int i = 0; i < Q; i++) { ll resp = pseg.prod(L[i]-1, R[i]), resq = qseg.prod(L[i]-1, R[i]); ll sp = p[S[i]-1], sq = q[S[i]-1]; if (resp < sq and resq > sp) ; //ok else ans[i] = false; //ng } } for (int i = 0; i < Q; i++) { cout << (ans[i]? "Yes" : "No") << endl; } }