結果

問題 No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
ユーザー gew1fw
提出日時 2025-06-12 19:05:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,564 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 210,452 KB
最終ジャッジ日時 2025-06-12 19:06:54
合計ジャッジ時間 10,821 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr += 1

    A = []
    T = []
    prefix_A = [0] * (N + 1)

    for i in range(N):
        a = int(input[ptr])
        t = int(input[ptr+1])
        ptr += 2
        A.append(a)
        T.append(t)
        prefix_A[i+1] = prefix_A[i] + a

    # Precompute low and high for each element
    low = [T[i] for i in range(N)]
    high = [T[i] + A[i] -1 if A[i] > 0 else T[i] for i in range(N)]
    A_values = A

    # Build segment tree
    class SegmentTreeNode:
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.left = None
            self.right = None
            self.data = []

        def add(self, idx, low_val, high_val, a_val):
            self.data.append( (low_val, high_val, a_val) )
            self.data.sort()

        def merge(self, left, right):
            self.data = []
            i = j = 0
            left_data = left.data
            right_data = right.data
            while i < len(left_data) and j < len(right_data):
                if left_data[i][0] < right_data[j][0]:
                    self.data.append(left_data[i])
                    i += 1
                else:
                    self.data.append(right_data[j])
                    j += 1
            while i < len(left_data):
                self.data.append(left_data[i])
                i += 1
            while j < len(right_data):
                self.data.append(right_data[j])
                j += 1

    # Function to build the segment tree
    def build(l, r):
        node = SegmentTreeNode(l, r)
        if l == r:
            # Add the element
            low_val = low[l]
            high_val = high[l]
            a_val = A_values[l]
            node.add(l, low_val, high_val, a_val)
            return node
        else:
            mid = (l + r) // 2
            node.left = build(l, mid)
            node.right = build(mid+1, r)
            node.merge(node.left, node.right)
            return node

    root = build(0, N-1)

    Q = int(input[ptr])
    ptr += 1

    for _ in range(Q):
        D = int(input[ptr])
        L = int(input[ptr+1])
        R = int(input[ptr+2])
        ptr += 3

        L -= 1
        R -= 1

        # Compute sum_A in [L, R]
        sum_A = prefix_A[R+1] - prefix_A[L]

        # Compute sum_s
        count1 = 0
        sum_T1 = 0
        sum_A2 = 0

        # Function to query the segment tree
        def query(node, l, r, D_val):
            nonlocal count1, sum_T1, sum_A2
            if node.r < l or node.l > r:
                return
            if l <= node.l and node.r <= r:
                # Process this node
                data = node.data
                # Find the index where low_i > D_val
                idx = bisect.bisect_right(data, (D_val, float('inf'), float('inf'))) 
                # All elements before idx have low_i <= D_val
                for i in range(idx):
                    low_i, high_i, a_i = data[i]
                    if D_val < high_i:
                        count1 +=1
                        sum_T1 += low_i
                    else:
                        sum_A2 += a_i
                return
            query(node.left, l, r, D_val)
            query(node.right, l, r, D_val)

        query(root, L, R, D)

        sum_part1 = (D + 1) * count1 - sum_T1
        sum_part2 = sum_A2
        sum_s = sum_part1 + sum_part2

        result = sum_A - sum_s
        print(result)

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