結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    
    elements_part1 = []
    elements_part2 = []
    for _ in range(N):
        A = int(data[idx])
        T = int(data[idx+1])
        idx +=2
        if A > 0:
            elements_part1.append((T, A))
            Y = A + T -1
            elements_part2.append((T, Y))
        else:
            elements_part1.append((0, 0))
            elements_part2.append((0, 0))
    
    class SegmentTreePart1:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<=1
            self.tree = [[] for _ in range(2*self.size)]
            for i in range(self.n):
                T, A = data[i]
                if A >0:
                    self.tree[self.size + i] = [(T, A)]
                else:
                    self.tree[self.size + i] = []
            for i in range(self.size-1, 0, -1):
                left = self.tree[2*i]
                right = self.tree[2*i+1]
                merged = []
                l = r =0
                while l < len(left) and r < len(right):
                    if left[l][0] < right[r][0]:
                        merged.append(left[l])
                        l +=1
                    else:
                        merged.append(right[r])
                        r +=1
                merged += left[l:]
                merged += right[r:]
                self.tree[i] = merged
            for i in range(1, 2*self.size):
                prefix = [0]
                for t, a in self.tree[i]:
                    prefix.append(prefix[-1] + a)
                self.tree[i] = (self.tree[i], prefix)
        
        def query(self, L, R, D):
            L += self.size
            R += self.size
            res =0
            while L <= R:
                if L %2 ==1:
                    arr, prefix = self.tree[L]
                    idx_t = bisect.bisect_right(arr, (D, float('inf')))
                    res += prefix[-1] - prefix[idx_t]
                    L +=1
                if R %2 ==0:
                    arr, prefix = self.tree[R]
                    idx_t = bisect.bisect_right(arr, (D, float('inf')))
                    res += prefix[-1] - prefix[idx_t]
                    R -=1
                L >>=1
                R >>=1
            return res
    
    class SegmentTreePart2:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<=1
            self.tree = [[] for _ in range(2*self.size)]
            for i in range(self.n):
                T, Y = data[i]
                if Y >0:
                    self.tree[self.size + i] = [(T, Y)]
                else:
                    self.tree[self.size + i] = []
            for i in range(self.size-1, 0, -1):
                left = self.tree[2*i]
                right = self.tree[2*i+1]
                merged = []
                l = r =0
                while l < len(left) and r < len(right):
                    if left[l][0] < right[r][0]:
                        merged.append(left[l])
                        l +=1
                    else:
                        merged.append(right[r])
                        r +=1
                merged += left[l:]
                merged += right[r:]
                self.tree[i] = merged
            for i in range(1, 2*self.size):
                arr = self.tree[i]
                Y_list = [y for t, y in arr]
                Y_list.sort()
                prefix = [0]
                for y in Y_list:
                    prefix.append(prefix[-1] + y)
                self.tree[i] = (arr, Y_list, prefix)
        
        def query(self, L, R, D):
            L += self.size
            R += self.size
            sum_Y =0
            count =0
            while L <= R:
                if L %2 ==1:
                    arr, Y_list, prefix = self.tree[L]
                    idx_t = bisect.bisect_right(arr, (D, float('inf')))
                    if idx_t >0:
                        y_sub = Y_list[:idx_t]
                        idx_y = bisect.bisect_right(y_sub, D)
                        sum_Y += prefix[idx_t] - prefix[idx_y]
                        count += idx_t - idx_y
                    L +=1
                if R %2 ==0:
                    arr, Y_list, prefix = self.tree[R]
                    idx_t = bisect.bisect_right(arr, (D, float('inf')))
                    if idx_t >0:
                        y_sub = Y_list[:idx_t]
                        idx_y = bisect.bisect_right(y_sub, D)
                        sum_Y += prefix[idx_t] - prefix[idx_y]
                        count += idx_t - idx_y
                    R -=1
                L >>=1
                R >>=1
            return sum_Y, count
    
    st_part1 = SegmentTreePart1(elements_part1)
    st_part2 = SegmentTreePart2(elements_part2)
    
    Q = int(data[idx])
    idx +=1
    for _ in range(Q):
        D = int(data[idx])
        L = int(data[idx+1])-1
        R = int(data[idx+2])-1
        idx +=3
        sum_p1 = st_part1.query(L, R, D)
        sum_p2, cnt_p2 = st_part2.query(L, R, D)
        total = sum_p1 + (sum_p2 - D * cnt_p2)
        print(total)

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