結果

問題 No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
ユーザー lam6er
提出日時 2025-04-09 20:57:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,112 bytes
コンパイル時間 453 ms
コンパイル使用メモリ 82,824 KB
実行使用メモリ 269,312 KB
最終ジャッジ日時 2025-04-09 21:00:34
合計ジャッジ時間 98,886 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    A = []
    T = []
    X = []
    for _ in range(N):
        a = int(input[ptr])
        ptr +=1
        t = int(input[ptr])
        ptr +=1
        A.append(a)
        T.append(t)
        X_i = t + a -1
        X.append(X_i)

    Q = int(input[ptr])
    ptr +=1
    queries = []
    for q in range(Q):
        D = int(input[ptr])
        L = int(input[ptr+1])
        R = int(input[ptr+2])
        ptr +=3
        queries.append((D, L-1, R-1, q))  # 0-based indices

    # Prepare prefix sums for original A
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]

    events = []
    for i in range(N):
        start_d = T[i] -1
        events.append((start_d, 0, i))
        end_d = X[i] +1
        events.append((end_d, 2, i))

    for q in queries:
        D_q, L_q, R_q, idx = q
        events.append((D_q, 1, (D_q, L_q, R_q, idx)))

    # Sort events:
    # primary key: D, secondary key: type (0,1,2)
    events.sort(key=lambda x: (x[0], x[1]))

    # Initialize BITs (1-based)
    class BIT:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(self.size + 2)
        def update(self, idx, val):
            while idx <= self.size:
                self.tree[idx] += val
                idx += idx & -idx
        def query(self, idx):
            res =0
            while idx >0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
        def range_query(self, l, r):
            return self.query(r) - self.query(l-1)

    # BIT for count in active1
    bit_cnt = BIT(N)
    # BIT for sum Ti in active1
    bit_ti = BIT(N)
    # BIT for sum A_i in active2
    bit_a2 = BIT(N)

    answer = [0]*Q

    for ev in events:
        D, typ, data = ev
        if typ ==0:
            # Add to active1: i is data
            i = data
            bit_cnt.update(i+1, 1)  # 1-based
            ti_val = T[i]
            bit_ti.update(i+1, ti_val)
        elif typ ==2:
            # Remove from active1, add to active2
            i = data
            bit_cnt.update(i+1, -1)
            ti_val = T[i]
            bit_ti.update(i+1, -ti_val)
            a_val = A[i]
            bit_a2.update(i+1, a_val)
        else:
            # Handle query
            D_q, L_q, R_q, q_idx = data
            L = L_q
            R = R_q
            # Convert to 1-based
            L_1 = L +1
            R_1 = R +1
            cnt1 = bit_cnt.range_query(L_1, R_1)
            sum_ti1 = bit_ti.range_query(L_1, R_1)
            sum_case1 = (D_q +1) * cnt1 - sum_ti1
            sum_a2 = bit_a2.range_query(L_1, R_1)
            sum_A_range = prefix[R_q+1] - prefix[L_q]
            ans = sum_A_range - (sum_case1 + sum_a2)
            answer[q_idx] = ans

    # Reorder answers based on original query order
    final = [0]*Q
    for q in queries:
        D_q, L_q, R_q, idx = q
        final[idx] = answer[idx]
    for ans in final:
        print(ans)

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