結果

問題 No.3314 Library Rearrangement
コンテスト
ユーザー 👑 ArcAki
提出日時 2025-05-04 03:11:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,301 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 168,272 KB
最終ジャッジ日時 2025-05-06 07:06:57
合計ジャッジ時間 11,330 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

# ChatGPT-o4-mini-highによる生成コード


import sys
def main():
    input = sys.stdin.readline

    N, K, Q = map(int, input().split())
    A = list(map(int, input().split()))

    # ---- 更新クエリ ----
    Lp = [0] * K
    Rp = [0] * K
    Cp = [0] * K
    for i in range(K):
        l, r, x = map(int, input().split())
        Lp[i] = l - 1
        Rp[i] = r
        Cp[i] = -x  # 符号反転して B[j] = min(B[j], -x)

    # ---- 質問クエリ ----
    Lq = [0] * Q
    Rq = [0] * Q
    Xq = [0] * Q
    for i in range(Q):
        l, r, x = map(int, input().split())
        Lq[i] = l - 1
        Rq[i] = r
        Xq[i] = x

    # ---- 初期プレフィックス和による前処理 ----
    P = [0] * (N + 1)
    for i in range(N):
        P[i + 1] = P[i] + A[i]

    # 並列二分探索の境界
    l_arr = [0] * Q
    r_arr = [K + 1] * Q
    # 初期和で条件を満たすものは答え＝0 に固定
    for i in range(Q):
        if P[Rq[i]] - P[Lq[i]] >= Xq[i]:
            r_arr[i] = 0

    # ---- セグメントツリービーツの構築 （B[j] = -A[j] で管理） ----
    S = 1 << (N - 1).bit_length()
    size = S
    size2 = 2 * size
    INF = 10**18

    max_init = [0] * size2
    smax_init = [0] * size2
    cnt_init = [0] * size2
    sum_init = [0] * size2

    # 葉の初期化
    for i in range(size):
        p = size + i
        if i < N:
            v = -A[i]
            max_init[p] = v
            smax_init[p] = -INF
            cnt_init[p] = 1
            sum_init[p] = v
        else:
            max_init[p] = -INF
            smax_init[p] = -INF
            cnt_init[p] = 1
            sum_init[p] = 0

    # 内部ノードを build
    for p in range(size - 1, 0, -1):
        L = p << 1
        R = L | 1
        if max_init[L] > max_init[R]:
            max_init[p] = max_init[L]
            cnt_init[p] = cnt_init[L]
            smax_init[p] = max(smax_init[L], max_init[R])
        elif max_init[L] < max_init[R]:
            max_init[p] = max_init[R]
            cnt_init[p] = cnt_init[R]
            smax_init[p] = max(smax_init[R], max_init[L])
        else:
            max_init[p] = max_init[L]
            cnt_init[p] = cnt_init[L] + cnt_init[R]
            smax_init[p] = max(smax_init[L], smax_init[R])
        sum_init[p] = sum_init[L] + sum_init[R]

    # ---- 並列二分探索ループ ----
    for _ in range((K + 1).bit_length()):
        # mid ごとにクエリを振り分け
        buckets = [[] for _ in range(K + 1)]
        any_pending = False
        for i in range(Q):
            if l_arr[i] + 1 < r_arr[i]:
                m = (l_arr[i] + r_arr[i]) >> 1
                buckets[m].append(i)
                any_pending = True
        if not any_pending:
            break

        # 各イテレーションでセグ木をリセット
        maxv = max_init[:]
        smaxv = smax_init[:]
        cntv = cnt_init[:]
        sumv = sum_init[:]

        # ビーツの push/pull
        def push(p):
            L = p << 1; R = L | 1
            if maxv[L] > maxv[p]:
                sumv[L] -= (maxv[L] - maxv[p]) * cntv[L]
                maxv[L] = maxv[p]
            if maxv[R] > maxv[p]:
                sumv[R] -= (maxv[R] - maxv[p]) * cntv[R]
                maxv[R] = maxv[p]

        def pull(p):
            L = p << 1; R = L | 1
            if maxv[L] > maxv[R]:
                maxv[p] = maxv[L]
                cntv[p] = cntv[L]
                smaxv[p] = max(smaxv[L], maxv[R])
            elif maxv[L] < maxv[R]:
                maxv[p] = maxv[R]
                cntv[p] = cntv[R]
                smaxv[p] = max(smaxv[R], maxv[L])
            else:
                maxv[p] = maxv[L]
                cntv[p] = cntv[L] + cntv[R]
                smaxv[p] = max(smaxv[L], smaxv[R])
            sumv[p] = sumv[L] + sumv[R]

        # chmin 更新
        def range_chmin(a, b, x, p=1, nl=0, nr=size):
            if a >= nr or b <= nl or maxv[p] <= x:
                return
            if a <= nl and nr <= b and smaxv[p] < x:
                sumv[p] -= (maxv[p] - x) * cntv[p]
                maxv[p] = x
                return
            push(p)
            mid = (nl + nr) >> 1
            lc = p << 1; rc = lc | 1
            range_chmin(a, b, x, lc, nl, mid)
            range_chmin(a, b, x, rc, mid, nr)
            pull(p)

        # 区間和取得
        def range_sum(a, b, p=1, nl=0, nr=size):
            if a >= nr or b <= nl:
                return 0
            if a <= nl and nr <= b:
                return sumv[p]
            push(p)
            mid = (nl + nr) >> 1
            return range_sum(a, b, p << 1, nl, mid) + range_sum(a, b, (p << 1) | 1, mid, nr)

        # 更新を順に適用しつつ、その時点で mid=i のクエリを評価
        for i in range(1, K + 1):
            range_chmin(Lp[i-1], Rp[i-1], Cp[i-1])
            for qi in buckets[i]:
                total = -range_sum(Lq[qi], Rq[qi])
                if total >= Xq[qi]:
                    r_arr[qi] = i
                else:
                    l_arr[qi] = i

    # ---- 出力 ----
    out = []
    for i in range(Q):
        ans = r_arr[i]
        if ans > K:
            ans = -1
        out.append(str(ans))
    sys.stdout.write("\n".join(out))


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