結果

問題 No.3214 small square
コンテスト
ユーザー norioc
提出日時 2026-11-19 00:05:22
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,339 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 81 ms
コンパイル使用メモリ 64,636 KB
実行使用メモリ 153,408 KB
最終ジャッジ日時 2026-11-19 00:06:23
合計ジャッジ時間 53,602 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

from bisect import bisect_left, bisect_right
from collections import defaultdict


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


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

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

    x = 2 * X
    y = 2 * Y
    d[2*X - 2*A].append((Y, V))
    d[2*X + 1].append((Y, -V))

    ys.append(Y-A)
    ys.append(Y+1)


# Y 座標 : 区間Add区間Maxで最大値を求める

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

ans = 0
sd = RangeAddRangeMax([0] * (2*N))
for x in sorted(d.keys()):
    ans = max(ans, sd.range_max(0, N))

    for y, v in d[x]:
        l = y2i[y-A]
        r = y2i[y+1]
        # print(f'{y=} {l=} {r=}')
        sd.range_add(l, r, v)

print(ans)
0