結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー gew1fw
提出日時 2025-06-12 16:50:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,898 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 121,216 KB
最終ジャッジ日時 2025-06-12 16:51:59
合計ジャッジ時間 7,393 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.ops = []

def build(l, r):
    node = SegmentTreeNode(l, r)
    if l == r:
        return node
    mid = (l + r) // 2
    node.left = build(l, mid)
    node.right = build(mid + 1, r)
    return node

def add_op(node, L, R, op):
    if node.r < L or node.l > R:
        return
    if L <= node.l and node.r <= R:
        node.ops.append(op)
        return
    add_op(node.left, L, R, op)
    add_op(node.right, L, R, op)

def sort_ops(node):
    node.ops.sort()
    if node.left:
        sort_ops(node.left)
    if node.right:
        sort_ops(node.right)

def collect_ops(node, i, ops_list):
    if node.r < i or node.l > i:
        return
    if node.l == node.r == i:
        ops_list.extend(node.ops)
        return
    collect_ops(node.left, i, ops_list)
    collect_ops(node.right, i, ops_list)
    ops_list.extend(node.ops)

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    K = int(input[ptr]); ptr +=1
    Q = int(input[ptr]); ptr +=1

    root = build(1, N)
    for k in range(K):
        Lk = int(input[ptr]); ptr +=1
        Rk = int(input[ptr]); ptr +=1
        Ck = int(input[ptr]); ptr +=1
        Hk = int(input[ptr]); ptr +=1
        add_op(root, Lk, Rk, (k, Ck, Hk))

    sort_ops(root)

    for _ in range(Q):
        Iq = int(input[ptr]); ptr +=1
        Xq = int(input[ptr]); ptr +=1
        x = Xq - 0.5
        ops = []
        collect_ops(root, Iq, ops)
        ops.sort()
        sum_h = 0
        ans = -1
        for k, Ck, Hk in ops:
            sum_h += Hk
            if sum_h >= x:
                ans = Ck
                break
        print(ans if ans != -1 else -1)

if __name__ == "__main__":
    main()
0