結果

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

ソースコード

diff # 

import sys
from sys import stdin
from bisect import bisect_right

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

class SegmentTree:
    def __init__(self, start, end):
        self.root = self.build(start, end)
    
    def build(self, l, r):
        node = SegmentTreeNode(l, r)
        if l == r:
            return node
        mid = (l + r) // 2
        node.left = self.build(l, mid)
        node.right = self.build(mid+1, r)
        return node
    
    def insert(self, node, L, R, c, h, k):
        if node.r < L or node.l > R:
            return
        if L <= node.l and node.r <= R:
            node.ops.append((k, h, c))
            return
        self.insert(node.left, L, R, c, h, k)
        self.insert(node.right, L, R, c, h, k)
    
    def query(self, I):
        res = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            if node.l > I or node.r < I:
                continue
            res.extend(node.ops)
            if node.left:
                stack.append(node.right)
                stack.append(node.left)
        res.sort()
        return res

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

    st = SegmentTree(1, N)
    ops = []
    for k in range(1, K+1):
        L = int(input[ptr])
        R = int(input[ptr+1])
        C = int(input[ptr+2])
        H = int(input[ptr+3])
        ptr +=4
        ops.append((L, R, C, H))
        st.insert(st.root, L, R, C, H, k)
    
    # Precompute prefix sums for each I
    prefix = {}
    for i in range(1, N+1):
        oplist = st.query(i)
        k_list = []
        sum_h = 0
        sum_list = [0]
        C_list = []
        for k, h, c in oplist:
            sum_h += h
            sum_list.append(sum_h)
            C_list.append(c)
        prefix[i] = (sum_list, C_list)
    
    # Process queries
    for _ in range(Q):
        I = int(input[ptr])
        X = int(input[ptr+1])
        ptr +=2
        t = X -0.5
        if I not in prefix or len(prefix[I][0]) ==0:
            print(-1)
            continue
        sum_list, C_list = prefix[I]
        total = sum_list[-1]
        if total <= t:
            print(-1)
            continue
        # Find the first sum >= t
        pos = bisect_right(sum_list, t) -1
        if pos < len(C_list):
            print(C_list[pos])
        else:
            print(-1)

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