結果
| 問題 | No.3214 small square |
| コンテスト | |
| ユーザー |
norioc
|
| 提出日時 | 2026-11-19 00:06:10 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 3,341 bytes |
| 記録 | |
| コンパイル時間 | 90 ms |
| コンパイル使用メモリ | 64,276 KB |
| 実行使用メモリ | 153,768 KB |
| 最終ジャッジ日時 | 2026-11-19 00:07:05 |
| 合計ジャッジ時間 | 47,808 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 WA * 23 |
ソースコード
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+1, v)
print(ans)
norioc