結果
問題 | 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) ; //okelse ans[i] = false; //ng}}for (int i = 0; i < Q; i++) {cout << (ans[i]? "Yes" : "No") << endl;}}