結果

問題 No.2662 Installing Cell Towers
ユーザー navel_tosnavel_tos
提出日時 2024-03-06 16:20:34
言語 PyPy3
(7.3.15)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,113 bytes
コンパイル時間 102 ms
最終ジャッジ日時 2024-09-29 18:16:37
合計ジャッジ時間 577 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
8628e2fec051
[/j_bin/judge_tool judge 0 30000 ../CompileMemory.txt /dev/null sud /dev/null _ pypy3 -mpy_compile Main.py]
open /home/yuki2006/gopath/src/yukicoder/judge/lang/lang.csv: no such file or directory
goroutine 1 [running]:
runtime/debug.Stack()
	/usr/local/go/src/runtime/debug/stack.go:24 +0x5e
main.main.func1()
	/home/yuki2006/gopath/src/yukicoder/judge/main.go:20 +0x57
panic({0x7661e0?, 0xc00006eb70?})
	/usr/local/go/src/runtime/panic.go:770 +0x132
yukicoder/env.InitLangCommands(0x0)
	/home/yuki2006/gopath/src/yukicoder/env/lang.go:57 +0x3a5
main.main()
	/home/yuki2006/gopath/src/yukicoder/judge/main.go:42 +0x65

ソースコード

diff # 

#yukicoder 2662 Installing Cell Towers

#Lazy Segment Tree
class LazySegmentTree:
    #適応条件: 値X, 遅延Lが (1)モノイド (2)単位元 (3)結合法則 (4)右作用可能
    def __init__(self, N, e_node, e_lazy, node_f, lazy_f, ref_f): self._N = N; self._height = (N - 1).bit_length(); self._size = 1 << self._height; self._e_node = e_node; self._e_lazy = e_lazy; self._node_f = node_f; self._lazy_f = lazy_f; self._ref_f = ref_f; self._node = [e_node] * 2 * self._size; self._lazy = [e_lazy] * 2 * self._size
    def build(self, array):
        assert len(array) == self._N, 'array too large'
        for i, v in enumerate(array, start = self._size): self._node[i] = v
        for i in range(self._size - 1, 0, -1): self._node[i] = self._node_f(self._node[i << 1], self._node[i << 1 | 1])
    def _ref_lazy(self, index): return self._ref_f(self._node[index], self._lazy[index])
    def _propagate_from_top(self, index):  #遅延評価・子へのpush  唯一遅延をresetする関数
        index += self._size
        for h in range(self._height, 0, -1):
            i = index >> h
            if self._lazy[i] != self._e_lazy: Lt, Rt = i << 1, i << 1 | 1; self._lazy[Lt] = self._lazy_f(self._lazy[Lt], self._lazy[i]); self._lazy[Rt] = self._lazy_f(self._lazy[Rt], self._lazy[i]); self._node[i] = self._ref_lazy(i); self._lazy[i] = self._e_lazy
    def _update_from_bottom(self, index):
        i = (index + self._size) >> 1
        while i > 0: self._node[i] = self._node_f(self._ref_lazy(i << 1), self._ref_lazy(i << 1 | 1)); i >>= 1
    def update(self, Lt, Rt, value):  #半開区間[Lt, Rt)に値valueを作用
        if Lt == Rt: return
        self._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Li, Ri = Lt + self._size, Rt + self._size
        while Li < Ri:
            if Li & 1: self._lazy[Li] = self._lazy_f(self._lazy[Li], value); Li += 1
            if Ri & 1: Ri -= 1; self._lazy[Ri] = self._lazy_f(self._lazy[Ri], value)
            Li >>= 1; Ri >>= 1
        self._update_from_bottom(Lt); self._update_from_bottom(Rt - 1)
    def fold(self, Lt, Rt):  #半開区間[Lt, Rt)の作用値を取得
        if Lt == Rt: return self._e_node
        self._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Lt, Rt = Lt + self._size, Rt + self._size; vL, vR = self._e_node, self._e_node
        while Lt < Rt:
            if Lt & 1: vL = self._node_f(vL, self._ref_lazy(Lt)); Lt += 1
            if Rt & 1: Rt -= 1; vR = self._node_f(self._ref_lazy(Rt), vR)
            Lt >>= 1; Rt >>= 1
        return self._node_f(vL, vR)


#入力受取
N, M = map(int, input().split())
P, Q = [], []
for _ in range(M):
    p, q = map(int, input().split())
    P.append(p)
    Q.append(q)

#区間加算のLazy SegTreeを定義  区間sumなのでnode値は(値, 該当ノード数)
def node_f(node1, node2):
    return (node1[0] + node2[0], node1[1] + node2[1])
def lazy_f(lazy1, lazy2):
    return lazy1 + lazy2
def ref_f(node, lazy):
    return (node[0] + node[1] * lazy, node[1])
LST = LazySegmentTree(N + 2, (0, 0), 0, node_f, lazy_f, ref_f)
LST.build([(0, 0)] + [(0, 1) for _ in range(N + 1)])

#imos法を応用した区間加算
for Pi, Qi in zip(P, Q):
    #1. B[Pi - Qi + 1, Pi) に+1  B[Pi]に-(Qi - 1)
    #2. B[Pi]に+Qi, B[Pi + 1, Pi + Qi + 1) に-1 の処理をしたい
    #区間端が超過するので注意して計算
    Lt = max(1, Pi - Qi)
    Lt_add = max(0, Lt + (Qi - Pi))
    Rt = min(N, Pi + Qi)  #右端は適当でよい(答えには影響しないため)
    LST.update(Lt, Lt + 1, + Lt_add)
    LST.update(Lt + 1, Pi + 1, + 1)
    LST.update(Pi + 1, Rt + 1, - 1)

#答えを出力
ans = [LST.fold(0, i + 1)[0] for i in range(N + 1)]
print(*ans[1:])



'''
ここからデバッグ用
'''

#愚直解
def brute(N, M, P, Q):
    A = [0] * (N + 1)
    for p, q in zip(P, Q):
        for j in range(1, N + 1):
            A[j] += max(0, q - abs(p - j))
    return A

def solve(N, M, P, Q):
    def node_f(node1, node2):
        return (node1[0] + node2[0], node1[1] + node2[1])
    def lazy_f(lazy1, lazy2):
        return lazy1 + lazy2
    def ref_f(node, lazy):
        return (node[0] + node[1] * lazy, node[1])
    LST = LazySegmentTree(N + 2, (0, 0), 0, node_f, lazy_f, ref_f)
    LST.build([(0, 0)] + [(0, 1) for _ in range(N + 1)])

    #imos法を応用した区間加算
    for Pi, Qi in zip(P, Q):
        Lt = max(1, Pi - Qi)
        Lt_add = max(0, Lt + (Qi - Pi))
        Rt = min(N, Pi + Qi)
        LST.update(Lt, Lt + 1, + Lt_add)
        LST.update(Lt + 1, Pi + 1, + 1)
        LST.update(Pi + 1, Rt + 1, - 1)

    #答えを出力
    ans = [LST.fold(0, i + 1)[0] for i in range(N + 1)]
    return ans

#random test
import random
def make_test(N = 10, M = 10):
    P = [random.randint(1, N) for _ in range(M)]
    Q = [random.randint(1, 10 ** 9) for _ in range(M)]
    return N, M, P, Q

def random_test(time):
    for t in range(1, time + 1):
        N, M, P, Q = make_test()
        if brute(N, M, P, Q) != solve(N, M, P, Q):
            print('WA in test', t)
            return N, M, P, Q
    print('AC')
    return [None] * 4
0