結果

問題 No.2860 Heal Slimes
コンテスト
ユーザー detteiuu
提出日時 2026-10-22 00:38:31
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,050 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 80 ms
コンパイル使用メモリ 64,744 KB
実行使用メモリ 89,584 KB
最終ジャッジ日時 2026-10-22 00:38:50
合計ジャッジ時間 10,724 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 55 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline

def op(x, y):
    return x+y
class SegTree:
    def __init__(self, init_val, op, ide_ele):
        n = len(init_val)
        self.n = n
        self.op = op
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]

    def update(self, l, r, x):
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.tree[l] = self.op(x, self.tree[l])
                l += 1
            if r & 1:
                self.tree[r - 1] = self.op(x, self.tree[r - 1])
            l >>= 1
            r >>= 1

    def query(self, k):
        ans = self.ide_ele
        k += self.num
        ans = self.op(ans, self.tree[k])
        while k > 1:
            ans = self.op(ans, self.tree[k>>1])
            k >>= 1
        return ans

for _ in range(int(input())):
    N, K, X = map(int, input().split())
    H = list(map(int, input().split()))

    if len(set([h%X for h in H])) != 1:
        print("No")
        continue

    for i in range(N): H[i] //= X

    A = [0]*K
    for i, h in enumerate(H):
        A[i%K] += h

    L, R = A[:N%K], A[N%K:]

    if len(L) == 0:
        if len(set(R)) == 1:
            for i in range(1, K):
                if H[i-1] < H[i]:
                    print("No")
                    break
                if H[-i] < H[-(i+1)]:
                    print("No")
                    break
            else:
                print("Yes")
        else:
            print("No")
        continue

    if len(set(L)) != 1 or len(set(R)) != 1:
        print("No")
        continue

    a, b = R[0], L[0]
    diff = b-a
    seg = SegTree(H, op, 0)
    for i in range(N-K+1):
        n = seg.query(i)
        if diff < n:
            print("No")
            break
        seg.update(i, i+K, diff-n)
    else:
        res = [seg.query(i) for i in range(N)]
        print("Yes" if res.count(diff) == N else "No")
0