結果

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

ソースコード

diff # 

import sys

class Node:
    __slots__ = ['l', 'r', 'left', 'right', 'sum', 'add']
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.sum = 0
        self.add = 0

def update(node, a, b, val):
    if node.r < a or node.l > b:
        return node
    new_node = Node(node.l, node.r)
    new_node.sum = node.sum
    new_node.add = node.add
    new_node.left = node.left
    new_node.right = node.right
    if a <= new_node.l and new_node.r <= b:
        new_node.sum += val * (new_node.r - new_node.l + 1)
        new_node.add += val
        return new_node
    mid = (new_node.l + new_node.r) // 2
    if new_node.left is None:
        new_node.left = Node(new_node.l, mid)
        new_node.right = Node(mid + 1, new_node.r)
    new_node.left = update(new_node.left, a, b, val)
    new_node.right = update(new_node.right, a, b, val)
    new_node.sum = new_node.left.sum + new_node.right.sum + new_node.add * (new_node.r - new_node.l + 1)
    return new_node

def query(node, i):
    if node is None or node.l > i or node.r < i:
        return 0
    res = node.add
    if node.l == node.r:
        return res
    mid = (node.l + node.r) // 2
    if i <= mid:
        res += query(node.left, i)
    else:
        res += query(node.right, i)
    return res

def main():
    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

    L = []
    R = []
    C = []
    H = []
    for _ in range(K):
        L_k = int(input[ptr])
        ptr += 1
        R_k = int(input[ptr])
        ptr += 1
        C_k = int(input[ptr])
        ptr += 1
        H_k = int(input[ptr])
        ptr += 1
        L.append(L_k)
        R.append(R_k)
        C.append(C_k)
        H.append(H_k)

    roots = [None] * (K + 1)
    roots[0] = Node(1, N)
    for j in range(1, K + 1):
        a = L[j-1]
        b = R[j-1]
        val = H[j-1]
        roots[j] = update(roots[j-1], a, b, val)

    for _ in range(Q):
        I_q = int(input[ptr])
        ptr += 1
        X_q = int(input[ptr])
        ptr += 1
        X = X_q - 0.5
        if K == 0:
            print(-1)
            continue
        low = 1
        high = K
        ans = -1
        while low <= high:
            mid = (low + high) // 2
            current_sum = query(roots[mid], I_q)
            if current_sum >= X:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        if ans == -1:
            print(-1)
        else:
            L_ans = L[ans-1]
            R_ans = R[ans-1]
            if L_ans <= I_q <= R_ans:
                print(C[ans-1])
            else:
                print(-1)

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