結果
| 問題 | No.2662 Installing Cell Towers |
| ユーザー |
 navel_tos
|
| 提出日時 | 2024-03-06 16:33:40 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,109 bytes |
| コンパイル時間 | 76 ms |
| 最終ジャッジ日時 | 2024-09-29 18:16:45 |
| 合計ジャッジ時間 | 590 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
2a0904a8e090
[/j_bin/judge_tool judge 0 30000 ../CompileMemory.txt /dev/null sud /dev/null _ pypy3 -mpy_compile Main.py]
open /home/yuki2006/gopath/src/yukicoder/judge/lang/lang.csv: no such file or directory
goroutine 1 [running]:
runtime/debug.Stack()
/usr/local/go/src/runtime/debug/stack.go:24 +0x5e
main.main.func1()
/home/yuki2006/gopath/src/yukicoder/judge/main.go:20 +0x57
panic({0x7661e0?, 0xc00006eb70?})
/usr/local/go/src/runtime/panic.go:770 +0x132
yukicoder/env.InitLangCommands(0x0)
/home/yuki2006/gopath/src/yukicoder/env/lang.go:57 +0x3a5
main.main()
/home/yuki2006/gopath/src/yukicoder/judge/main.go:42 +0x65
ソースコード
#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)
#区間への直線加算と解釈する
#A[j] += + j + (Qi - Pi) if Pi - Qi <= j < Pi
#A[j] += - j + (Qi + Pi) if Pi <= j <= Pi + Qi
#となるが、これはx軸をj, y軸をA[j]とみた直線の式となる
#y = ax + b と y = cx + dの合成結果は y = (a + c)x + (b + d)なので、遅延セグ木に乗る
def node_f(node1, node2):
a, b = node1
c, d = node2
return (a + c, b + d)
def lazy_f(lazy1, lazy2): #node_f と処理内容は同一
a, b = lazy1
c, d = lazy2
return (a + c, b + d)
def ref_f(node, lazy): #node_f と同一
a, b = node
c, d = lazy
return (a + c, b + d)
LST = LazySegmentTree(N + 1, (0, 0), (0, 0), node_f, lazy_f, ref_f)
for Pi, Qi in zip(P, Q):
Lt, Rt = max(1, Pi - Qi), min(N, Pi + Qi) + 1
#1. A[j] += + j + (Qi - Pi) if Pi - Qi <= j < Pi
LST.update(Lt, Pi, (1, Qi - Pi))
#2. A[j] += - j + (Qi + Pi) if Pi <= j <= Pi + Qi
LST.update(Pi, Rt, (-1, Qi + Pi))
#答えを出力
ans = [0] * (N + 1)
for i in range(1, N + 1):
a, b = LST.fold(i, i + 1)
ans[i] = a * i + b
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
def solve_2(N, M, P, Q):
def node_f(node1, node2):
a, b = node1
c, d = node2
return (a + c, b + d)
def lazy_f(lazy1, lazy2): #node_f と処理内容は同一
a, b = lazy1
c, d = lazy2
return (a + c, b + d)
def ref_f(node, lazy): #node_f と同一
a, b = node
c, d = lazy
return (a + c, b + d)
LST = LazySegmentTree(N + 1, (0, 0), (0, 0), node_f, lazy_f, ref_f)
for Pi, Qi in zip(P, Q):
Lt, Rt = max(1, Pi - Qi), min(N, Pi + Qi) + 1
#1. A[j] += + j + (Qi - Pi) if Pi - Qi <= j < Pi
LST.update(Lt, Pi, (1, Qi - Pi))
#2. A[j] += - j + (Qi + Pi) if Pi <= j <= Pi + Qi
LST.update(Pi, Rt, (-1, Qi + Pi))
#答えを出力
ans = [0] * (N + 1)
for i in range(1, N + 1):
a, b = LST.fold(i, i + 1)
ans[i] = a * i + b
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_2(N, M, P, Q):
print('WA in test', t)
return N, M, P, Q
print('AC')
return [None] * 4