結果

問題 No.1982 [Cherry 4th Tune B] 絶険
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:18:53
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,398 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 794,396 KB
最終ジャッジ日時 2025-04-15 22:20:22
合計ジャッジ時間 10,726 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 MLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

def build(l, r):
    if l == r:
        return Node(sum=0)
    mid = (l + r) // 2
    left = build(l, mid)
    right = build(mid+1, r)
    return Node(left=left, right=right, sum=0)

def update(node, l, r, ul, ur, val):
    if ur < l or r < ul:
        return node
    new_node = Node(left=node.left, right=node.right, sum=node.sum, lazy=node.lazy)
    if ul <= l and r <= ur:
        new_node.sum += val * (r - l + 1)
        new_node.lazy += val
        return new_node
    mid = (l + r) // 2
    if new_node.lazy != 0:
        new_left = Node(left=new_node.left.left, right=new_node.left.right, sum=new_node.left.sum, lazy=new_node.left.lazy)
        new_left.sum += new_node.lazy * (mid - l + 1)
        new_left.lazy += new_node.lazy
        new_right = Node(left=new_node.right.left, right=new_node.right.right, sum=new_node.right.sum, lazy=new_node.right.lazy)
        new_right.sum += new_node.lazy * (r - mid)
        new_right.lazy += new_node.lazy
        new_node.left = new_left
        new_node.right = new_right
        new_node.lazy = 0
    new_node.left = update(new_node.left, l, mid, ul, ur, val)
    new_node.right = update(new_node.right, mid+1, r, ul, ur, val)
    new_node.sum = new_node.left.sum + new_node.right.sum
    return new_node

def query(node, l, r, pos):
    if l == r:
        return node.sum
    mid = (l + r) // 2
    if node.lazy != 0:
        new_left = Node(left=node.left.left, right=node.left.right, sum=node.left.sum, lazy=node.left.lazy)
        new_left.sum += node.lazy * (mid - l + 1)
        new_left.lazy += node.lazy
        new_right = Node(left=node.right.left, right=node.right.right, sum=node.right.sum, lazy=node.right.lazy)
        new_right.sum += node.lazy * (r - mid)
        new_right.lazy += node.lazy
        node.left = new_left
        node.right = new_right
        node.lazy = 0
    if pos <= mid:
        return query(node.left, l, mid, pos)
    else:
        return query(node.right, mid+1, r, pos)

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

    ops = []
    for _ in range(K):
        L = int(data[ptr])
        ptr += 1
        R = int(data[ptr])
        ptr += 1
        C = int(data[ptr])
        ptr += 1
        H = int(data[ptr])
        ptr += 1
        ops.append((L, R, C, H))

    queries = []
    for _ in range(Q):
        I = int(data[ptr])
        ptr += 1
        X = int(data[ptr])
        ptr += 1
        queries.append((I, X))

    versions = [build(1, N)]
    for L, R, C, H in ops:
        versions.append(update(versions[-1], 1, N, L, R, H))

    for I, X in queries:
        T = X - 0.5
        total = query(versions[-1], 1, N, I)
        if total < T:
            print(-1)
            continue
        low, high = 1, K
        ans = K
        while low <= high:
            mid = (low + high) // 2
            s = query(versions[mid], 1, N, I)
            if s >= T:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        print(ops[ans-1][2])

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