結果
問題 |
No.2885 Range Triangle Collision Decision Queries
|
ユーザー |
![]() |
提出日時 | 2024-08-24 03:33:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,042 ms / 3,000 ms |
コード長 | 1,563 bytes |
コンパイル時間 | 3,209 ms |
コンパイル使用メモリ | 255,716 KB |
実行使用メモリ | 21,784 KB |
最終ジャッジ日時 | 2024-09-07 19:40:02 |
合計ジャッジ時間 | 55,259 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
コンパイルメッセージ
main.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 32 | main() { | ^~~~ main.cpp: In function 'std::pair<long long int, long long int> convert(ll, ll, ll, int)': main.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type] 20 | } | ^
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/segtree> 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}; } } //{l, r} に対して、{lmax, rmin} を返す pair<ll, ll> op(pair<ll, ll> a, pair<ll, ll> b) { return {max(a.first, b.first), min(a.second, b.second)}; } pair<ll, ll> e() { const ll INF = 4e18; return {-INF, INF}; } 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<pair<ll, ll>> pq(N); for (int i = 0; i < N; i++) { pq[i] = convert(A[i], B[i], D[i], k); } atcoder::segtree<pair<ll, ll>, op, e> seg(pq); for (int i = 0; i < Q; i++) { auto[resp, resq] = seg.prod(L[i]-1, R[i]); auto[sp, sq] = pq[S[i]-1]; if (resp < sq && resq > sp) ; //ok else ans[i] = false; //ng } } for (int i = 0; i < Q; i++) { cout << (ans[i]? "Yes" : "No") << endl; } }