結果

問題 No.2885 Range Triangle Collision Decision Queries
ユーザー Rac
提出日時 2025-02-01 13:41:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,221 bytes
コンパイル時間 579 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 260,744 KB
最終ジャッジ日時 2025-02-01 13:42:31
合計ジャッジ時間 44,513 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 41 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from sys import stdin

# 入力読み込み（高速なため sys.stdin.buffer を利用）
data = sys.stdin.buffer.read().split()
it = iter(data)
def next_int():
    return int(next(it))

# 入力
N = next_int()
A = [0]*N
B = [0]*N
D = [0]*N
for i in range(N):
    A[i] = next_int()
    B[i] = next_int()
    D[i] = next_int()

# 各三角形のパラメータ
L_arr = [A[i] - B[i] for i in range(N)]
R_arr = [A[i] + B[i] for i in range(N)]
X_arr = [B[i] - D[i] for i in range(N)]

# Sparse Table を作るための一般関数
def build_sparse_table(arr, func):
    n = len(arr)
    logn = math.floor(math.log2(n)) + 1
    st = [arr.copy()]
    for k in range(1, logn):
        prev = st[k-1]
        curr = [func(prev[i], prev[i + (1 << (k-1))])
                for i in range(n - (1 << k) + 1)]
        st.append(curr)
    return st

# Query: 区間 [l, r] (0-index) に対して st を使い func(…) を返す
def query_sparse(st, l, r, func):
    length = r - l + 1
    k = length.bit_length() - 1  # floor(log2(length))
    return func(st[k][l], st[k][r - (1 << k) + 1])

# Sparse Table の構築
st_max_L = build_sparse_table(L_arr, max)   # 区間最大
st_min_R = build_sparse_table(R_arr, min)   # 区間最小
st_max_X = build_sparse_table(X_arr, max)   # 区間最大

Q = next_int()
out_lines = []
for _ in range(Q):
    S = next_int()   # 1-indexed
    Lq = next_int()
    Rq = next_int()
    s_idx = S - 1
    l_idx = Lq - 1
    r_idx = Rq - 1

    # 区間 [l_idx, r_idx] 内の各パラメータの値
    seg_max_L = query_sparse(st_max_L, l_idx, r_idx, max)
    seg_min_R = query_sparse(st_min_R, l_idx, r_idx, min)
    seg_max_X = query_sparse(st_max_X, l_idx, r_idx, max)

    # T[S] のパラメータ
    L_S = L_arr[s_idx]
    R_S = R_arr[s_idx]
    X_S = X_arr[s_idx]

    L_val = L_S if L_S >= seg_max_L else seg_max_L  # = max(L_S, seg_max_L)
    R_val = R_S if R_S <= seg_min_R else seg_min_R  # = min(R_S, seg_min_R)
    X_val = X_S if X_S >= seg_max_X else seg_max_X  # = max(X_S, seg_max_X)

    # 条件チェック
    if R_val - L_val > 2 * X_val:
        out_lines.append("Yes")
    else:
        out_lines.append("No")

sys.stdout.write("\n".join(out_lines))
0