結果

問題 No.1982 [Cherry 4th Tune B] 絶険
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:10:53
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,142 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 856,648 KB
最終ジャッジ日時 2025-06-12 18:12:56
合計ジャッジ時間 8,312 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)

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

class SegmentTree:
    def __init__(self, l, r):
        self.root = self.build(l, r)
    
    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, j):
        if node.r < l or node.l > r:
            return
        if l <= node.l and node.r <= r:
            node.ops.append(j)
            return
        self.insert(node.left, l, r, j)
        self.insert(node.right, l, r, j)
    
    def query(self, node, i, result):
        if node.l > i or node.r < i:
            return
        result.extend(node.ops)
        if node.l == node.r:
            return
        self.query(node.left, i, result)
        self.query(node.right, i, result)

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
    
    operations = []
    for _ in range(K):
        L = int(input[ptr])
        ptr +=1
        R = int(input[ptr])
        ptr +=1
        C = int(input[ptr])
        ptr +=1
        H = int(input[ptr])
        ptr +=1
        operations.append( (L, R, C, H) )
    
    # Build segment tree
    st = SegmentTree(1, N)
    for j in range(K):
        L, R, C, H = operations[j]
        st.insert(st.root, L, R, j)
    
    # Prepare prefix sums and colors for each i
    prefix_sums = [[] for _ in range(N+1)]  # 1-based indexing
    colors = [[] for _ in range(N+1)]
    
    for i in range(1, N+1):
        j_list = []
        st.query(st.root, i, j_list)
        # Sort the j's to ensure they are in order
        j_list.sort()
        # Now, compute prefix sums and colors
        current_sum = 0
        ps = []
        cs = []
        for j in j_list:
            L_j, R_j, C_j, H_j = operations[j]
            current_sum += H_j
            ps.append(current_sum)
            cs.append(C_j)
        prefix_sums[i] = ps
        colors[i] = cs
    
    # Process queries
    for _ in range(Q):
        I = int(input[ptr])
        ptr +=1
        X = int(input[ptr])
        ptr +=1
        X_val = X - 0.5
        ps = prefix_sums[I]
        cs = colors[I]
        if not ps:
            print(-1)
            continue
        total = ps[-1]
        if total < X_val:
            print(-1)
            continue
        # Binary search
        left = 0
        right = len(ps) -1
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if ps[mid] >= X_val:
                ans = mid
                right = mid -1
            else:
                left = mid +1
        if ans == -1:
            print(-1)
        else:
            print(cs[ans])

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