結果

問題 No.2885 Range Triangle Collision Decision Queries
ユーザー Rac
提出日時 2025-02-01 13:37:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,737 bytes
コンパイル時間 711 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 52,352 KB
最終ジャッジ日時 2025-02-01 13:38:04
合計ジャッジ時間 14,988 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.data = [[] for _ in range(4 * n)]

    def build(self, index, l, r, triangles):
        if l == r:
            self.data[index] = [triangles[l]]
            return
        mid = (l + r) // 2
        self.build(2 * index + 1, l, mid, triangles)
        self.build(2 * index + 2, mid + 1, r, triangles)
        self.data[index] = sorted(self.data[2 * index + 1] + self.data[2 * index + 2])
    
    def query(self, index, l, r, ql, qr, x_range):
        if r < ql or qr < l:
            return False
        if ql <= l and r <= qr:
            left, right = x_range
            return any(left < x2 and x1 < right for x1, x2 in self.data[index])
        mid = (l + r) // 2
        return self.query(2 * index + 1, l, mid, ql, qr, x_range) or self.query(2 * index + 2, mid + 1, r, ql, qr, x_range)


def solve():
    input = sys.stdin.read
    data = input().split() 
    index = 0
    
    N = int(data[index])
    index += 1
    triangles = []
    for i in range(N):
        A, B, D = map(int, data[index:index+3])
        index += 3
        triangles.append((A - D, A + D, B - D, B))
    
    triangles.sort()  # x座標の左端でソート
    segment_tree = SegmentTree(N)
    segment_tree.build(0, 0, N - 1, [(x1, x2) for x1, x2, _, _ in triangles])
    
    Q = int(data[index])
    index += 1
    results = []
    for _ in range(Q):
        S, L, R = map(int, data[index:index+3])
        index += 3
        S -= 1; L -= 1; R -= 1
        sx1, sx2, sy1, sy2 = triangles[S]
        found = segment_tree.query(0, 0, N - 1, L, R, (sx1, sx2))
        results.append("Yes" if found else "No")
    
    sys.stdout.write("\n".join(results) + "\n")
0