結果

問題 No.3214 small square
ユーザー LyricalMaestro
提出日時 2025-10-11 19:52:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,526 ms / 3,000 ms
コード長 4,716 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 272,552 KB
最終ジャッジ日時 2025-10-11 19:54:04
合計ジャッジ時間 66,766 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/3214

from collections import deque

MIN_VALUE = -10 ** 18

class LazySegmentTree:
    """
    非再帰版遅延セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    取得のところの都合で取得演算子は可換になっている必要がある。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [MIN_VALUE] * (2 * self.size)
        self.lazy_array = [0 for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i] = a
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self.array[i] = max(self.array[2 * i], self.array[2 * i + 1])
            end_index = start_index
            start_index = end_index // 2
    
    def _propagates(self, *ids):
        for i in reversed(ids):
            self._propagate(i)

    def _propagate(self, i):
        v = self.lazy_array[i]
        if v == 0:
            return
        
        if i < self.size:
            self.lazy_array[2 * i] += v
            self.lazy_array[2 * i + 1] += v
            self.array[2 * i] += v
            self.array[2 * i + 1] += v
        self.lazy_array[i] = 0

    def _get_target_index(self, l, r):
        L = l + self.size; R = r + self.size
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while 0 < L and L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L > 0:
            yield L
            L >>= 1

    def add(self, l, r, x):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.size + l; R = self.size + r
        *ids, = self._get_target_index(l, r)
        self._propagates(*ids)
        while L < R:
            if R & 1:
                R -= 1
                self.lazy_array[R] += x
                self.array[R] += x
            if L & 1:
                self.lazy_array[L] += x
                self.array[L] += x
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            if i < self.size:
                self.array[i] = max(self.array[2 * i], self.array[2 * i +  1])

    def get_max(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self._propagates(*self._get_target_index(l, r))
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = MIN_VALUE
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.array[R])
            if L & 1:
                s = max(s, self.array[L])
                L += 1
            L >>= 1; R >>= 1
        return s



def main():
    N, A = map(int, input().split())
    xyv = []
    for _ in range(N):
        x, y, v = map(int, input().split())
        xyv.append((2 * x, 2 * y, v))
    
    # Y座標について座標圧縮
    y_set = set()
    for _, y, _ in xyv:
        y_set.add(y)
        y_set.add(y + 2 * A)
        y_set.add(y + 1)
        y_set.add(y + 2 * A + 1)
        y_set.add(y - 1)
        y_set.add(y + 2 * A - 1)
    y_list = list(y_set)
    y_list.sort()
    y_map = {}
    for i, y in enumerate(y_list):
        y_map[y] = i
    y_max = len(y_list)

    layz_seg_tree = LazySegmentTree([0] * y_max)

    x_map = {}
    x_keys = set()
    for x, y, v in xyv:
        if x not in x_map:
            x_map[x] = []
        x_map[x].append((y, v))
        x_keys.add(x + 1)
        x_keys.add(x)
        x_keys.add(x - 1)
        x_keys.add(x + 2 * A + 1)
        x_keys.add(x + 2 * A)
        x_keys.add(x + 2 * A - 1)

    x_list = list(x_keys)
    x_list.sort()    
    
    queue = deque()
    answer = 0
    for x in x_list:
        while len(queue) > 0 and queue[0][0] < (x - 2 * A):
            _, old_y_array = queue.popleft()

            for y, v in old_y_array:
                y_ = y_map[y]
                y1 = y_map[y + 2 * A]
                layz_seg_tree.add(y_, y1 + 1, -v)
        
        if x in x_map:
            y_array = x_map[x]
            for y, v in y_array:
                y_ = y_map[y]
                y2 = y_map[y + 2 * A]
                layz_seg_tree.add(y_, y2 + 1, v)
            queue.append((x, y_array))
        ans = layz_seg_tree.get_max(0, layz_seg_tree.size)
        answer = max(ans, answer)

    print(answer)












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