結果

問題 No.3214 small square
コンテスト
ユーザー norioc
提出日時 2026-11-18 03:33:59
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 4,149 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 187 ms
コンパイル使用メモリ 64,684 KB
実行使用メモリ 95,352 KB
最終ジャッジ日時 2026-11-18 03:35:16
合計ジャッジ時間 74,004 ms
ジャッジサーバーID
(参考情報)
judge5_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 31 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

from bisect import bisect_left, bisect_right
from collections import deque


def find_interval(slis: list, lo: int, hi: int) -> tuple[int, int, int]:
    """
    ソート済み slis に対して、lo <= x <= hi を満たす要素の個数と範囲を返す

    Returns:
        範囲内の個数, l, r
    """
    assert lo <= hi
    l = bisect_left(slis, lo)
    r = bisect_right(slis, hi)
    count = r-l
    if count <= 0:
        return 0, -1, -1  # no interval

    return count, l, r-1


class RangeAddRangeMax:
    B = 512  # 一つのバケット幅

    def __init__(self, a: list):
        n = len(a)
        bsize = (n + self.B - 1) // self.B
        # self.buckets = [0] * bsize
        self.add_buckets = [0] * bsize  # バケットへの加算
        self.max_buckets = [0] * bsize  # バケットの最大値
        self.data = a.copy()
        for i in range(bsize):
            start = i * self.B
            stop = min(n, (i+1) * self.B)
            self.max_buckets[i] = max([a[i] for i in range(start, stop)])

    def range_add(self, l: int, r: int, x: int):
        """[l, r) に x を加算"""
        assert 0 <= l < r <= len(self.data)

        for k in range(l // self.B, len(self.max_buckets)):
            nl = k * self.B
            nr = (k+1) * self.B
            if r <= nl: break

            if l <= nl and nr <= r:
                self.add_buckets[k] += x
                self.max_buckets[k] += x
            else:
                start = max(l, nl)
                stop = min(r, nr, len(self.data))
                for i in range(start, stop):
                    self.data[i] += x
                # バケットの最大値の更新
                self.max_buckets[k] = -INF
                for i in range(nl, min(nr, len(self.data))):
                    s = self.add_buckets[k] + self.data[i]
                    self.max_buckets[k] = max(self.max_buckets[k], s)

    def range_max(self, l: int, r: int) -> int:
        """[l, r) の最大値"""
        assert 0 <= l < r <= len(self.data)

        res = -INF
        for k in range(l // self.B, len(self.max_buckets)):
            nl = k * self.B
            nr = (k+1) * self.B
            if r <= nl: break

            if l <= nl and nr <= r:
                res = max(res, self.max_buckets[k])
            else:
                start = max(l, nl)
                stop = min(r, nr, len(self.data))
                for i in range(start, stop):
                    res = max(res, self.add_buckets[k] + self.data[i])

        return res


def shakutori(a: list, factory):
    n = len(a)
    state = factory()
    hi = -1
    for lo in range(n):
        if lo > hi:
            hi = lo - 1
            state = factory()

        # できるだけ伸ばす
        while hi+1 < n and state.can_expand(a[hi+1]):
            state.expand(a[hi+1])
            hi += 1

        if lo <= hi:
            yield state, lo, hi
            state.shrink(a[lo])


class WindowState:
    def __init__(self):
        self.sd = RangeAddRangeMax([0] * N)
        self.q = deque()

    def can_expand(self, v) -> bool:
        if len(self.q) == 0:
            return True

        x, _, _ = v
        return x - self.q[0][0] <= A

    def expand(self, v):
        self.q.append(v)

        _, y, val = v
        cnt, l, r = find_interval(ys, y-A, y)
        if cnt > 0:
            self.sd.range_add(l, r+1, val)

    def shrink(self, v):
        assert len(self.q) > 0
        assert self.q[0] == v
        self.q.popleft()

        _, y, val = v
        cnt, l, r = find_interval(ys, y-A, y)
        if cnt > 0:
            self.sd.range_add(l, r+1, -val)


INF = 1 << 62
N, A = map(int, input().split())

ps = []
for _ in range(N):
    X, Y, V = map(int, input().split())
    ps.append((X, Y, V))
ps.sort()

# X 座標 : しゃくとり法で点を集める
# Y 座標 : 区間Add区間Maxで最大値を求める

# Y 座標の全ての点を昇順で持ち、インデックス計算できるようにする
ys = sorted(set(y for _, y, _ in ps))

ans = 0
for st, _, _ in shakutori(ps, WindowState):
    res = st.sd.range_max(0, N)
    ans = max(ans, res)

print(ans)
0