結果

問題 No.2662 Installing Cell Towers
ユーザー navel_tos
提出日時 2024-03-06 16:20:34
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,265 ms / 2,000 ms
コード長 5,113 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,653 ms
コンパイル使用メモリ 81,888 KB
実行使用メモリ 132,868 KB
最終ジャッジ日時 2026-02-23 12:37:28
合計ジャッジ時間 11,948 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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