結果
問題 | No.1008 Bench Craftsman |
ユーザー |
![]() |
提出日時 | 2023-12-29 23:18:11 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,361 bytes |
コンパイル時間 | 597 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 115,112 KB |
最終ジャッジ日時 | 2024-09-27 16:24:56 |
合計ジャッジ時間 | 5,101 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 2 TLE * 1 -- * 24 |
ソースコード
import sysinput = sys.stdin.readlineclass LazySegmentTree:def __init__(self,n,identity_e_node,identity_e_lazy,combine_node_f,combine_lazy_f,reflect_f,):self._n = nself._size = 1self._height = 0while self._size < self._n:self._size <<= 1self._height += 1self._identity_e_node = identity_e_nodeself._identity_e_lazy = identity_e_lazyself._combine_node_f = combine_node_fself._combine_lazy_f = combine_lazy_fself._reflect_f = reflect_fself._node = [self._identity_e_node] * (2 * self._size)self._lazy = [self._identity_e_lazy] * (2 * self._size)#遅延データの値を値データに反映させたときの値を返す。def _reflect_lazy(self, index):return self._reflect_f(self._node[index], self._lazy[index])def _propagate_from_top(self, index):index += self._sizefor h in range(self._height, 0, -1):i = index >> hif self._lazy[i] != self._identity_e_lazy:self._lazy[i << 1] = self._combine_lazy_f(self._lazy[i << 1], self._lazy[i])self._lazy[i << 1 | 1] = self._combine_lazy_f(self._lazy[i << 1 | 1], self._lazy[i])self._node[i] = self._reflect_lazy(i)self._lazy[i] = self._identity_e_lazydef _update_from_bottom(self, index):index = (index + self._size) >> 1while index:self._node[index] = self._combine_node_f(self._reflect_lazy(index << 1),self._reflect_lazy(index << 1 | 1))index >>= 1def build(self, array):assert len(array) == self._nfor index, value in enumerate(array, start=self._size):self._node[index] = valuefor index in range(self._size - 1, 0, -1):self._node[index] = self._combine_node_f(self._node[index << 1],self._node[index << 1 | 1])# 区間更新 位置[L, R) (0-indexed)を値valueで更新def update(self, L, R, value):self._propagate_from_top(L)self._propagate_from_top(R - 1)L_lazy = L + self._sizeR_lazy = R + self._sizewhile L_lazy < R_lazy:if L_lazy & 1:self._lazy[L_lazy] = self._combine_lazy_f(self._lazy[L_lazy], value)L_lazy += 1if R_lazy & 1:R_lazy -= 1self._lazy[R_lazy] = self._combine_lazy_f(self._lazy[R_lazy], value)L_lazy >>= 1R_lazy >>= 1self._update_from_bottom(L)self._update_from_bottom(R - 1)# 区間取得 区間[L, R) (0-indexed)内の要素について# L番目から順にcombine_node_fを適用した値を返す。def fold(self, L, R):self._propagate_from_top(L)self._propagate_from_top(R - 1)L += self._sizeR += self._sizevalue_L = self._identity_e_nodevalue_R = self._identity_e_nodewhile L < R:if L & 1:value_L = self._combine_node_f(value_L, self._reflect_lazy(L))L += 1if R & 1:R -= 1value_R = self._combine_node_f(self._reflect_lazy(R), value_R)L >>= 1R >>= 1return self._combine_node_f(value_L, value_R)def g(v, s):return v * N + sdef g2(x):v, s = divmod(x, N)return (v, s)def op(x1, x2):v1, s1 = g2(x1)v2, s2 = g2(x2)return g(v1 + v2, s1 + s2)def reflect_f(node_, lazy):node = g2(node_)return g(node[0] + lazy * node[1], node[1])N, M = map(int, input().split())A = list(map(int, input().split()))X, W = [0] * M, [0] * Mfor i in range(M):X[i], W[i] = map(int, input().split())X[i] -= 1from operator import adddef f(l, vl, r, vr, c, T):T.update(l+1, r+1, c)T.update(l, l + 1, vl)T.update(r+1, r + 2, -vr)return Tdef printT(T):ans = []for i in range(N):ans.append(g2(T.fold(0, i + 1))[0])print("test", *ans)def check(m):T = LazySegmentTree(N+1,0,0,op,add,reflect_f)T.build([1 for _ in range(N + 1)])for x, w in zip(X, W):d = w // mr = min(x + d, N - 1)v = w - (r - x) * mT = f(x, w, r, v, -m, T)# printT(T)w -= mx -= 1if w <= 0 or x < 0:continuel = max(0, x - d)v = w - (x - l) * mT = f(l, v, x, w, m, T)# printT(T)for i in range(N):v = g2(T.fold(0, i + 1))[0]if v >= A[i]:return Falsereturn Truesw = sum(W)flag = 1for i in range(N):if A[i] <= sw:flag = 0if flag:print(0)exit()yes = 10 ** 9 + 5no = 0if not check(yes):print(-1)exit()while yes - no != 1:mid = (yes + no)//2if check(mid):yes = midelse:no = midprint(yes)