結果
問題 | No.2657 Falling Block Game |
ユーザー | ニックネーム |
提出日時 | 2024-03-01 23:49:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,562 ms / 2,000 ms |
コード長 | 1,627 bytes |
コンパイル時間 | 3,118 ms |
コンパイル使用メモリ | 81,444 KB |
実行使用メモリ | 102,212 KB |
最終ジャッジ日時 | 2024-03-01 23:49:43 |
合計ジャッジ時間 | 31,171 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
53,460 KB |
testcase_01 | AC | 38 ms
53,460 KB |
testcase_02 | AC | 36 ms
53,460 KB |
testcase_03 | AC | 37 ms
53,460 KB |
testcase_04 | AC | 189 ms
91,236 KB |
testcase_05 | AC | 1,562 ms
91,388 KB |
testcase_06 | AC | 1,193 ms
90,120 KB |
testcase_07 | AC | 1,529 ms
90,844 KB |
testcase_08 | AC | 870 ms
80,224 KB |
testcase_09 | AC | 374 ms
91,900 KB |
testcase_10 | AC | 842 ms
101,952 KB |
testcase_11 | AC | 811 ms
101,956 KB |
testcase_12 | AC | 882 ms
102,076 KB |
testcase_13 | AC | 841 ms
101,952 KB |
testcase_14 | AC | 837 ms
101,956 KB |
testcase_15 | AC | 830 ms
101,956 KB |
testcase_16 | AC | 841 ms
101,956 KB |
testcase_17 | AC | 847 ms
101,964 KB |
testcase_18 | AC | 850 ms
102,088 KB |
testcase_19 | AC | 829 ms
102,212 KB |
testcase_20 | AC | 824 ms
83,080 KB |
testcase_21 | AC | 793 ms
82,928 KB |
testcase_22 | AC | 834 ms
82,912 KB |
testcase_23 | AC | 828 ms
83,080 KB |
testcase_24 | AC | 798 ms
83,084 KB |
testcase_25 | AC | 795 ms
82,812 KB |
testcase_26 | AC | 820 ms
83,060 KB |
testcase_27 | AC | 818 ms
83,332 KB |
testcase_28 | AC | 795 ms
82,744 KB |
testcase_29 | AC | 855 ms
82,960 KB |
testcase_30 | AC | 480 ms
93,216 KB |
testcase_31 | AC | 545 ms
93,528 KB |
testcase_32 | AC | 509 ms
93,332 KB |
testcase_33 | AC | 526 ms
93,440 KB |
testcase_34 | AC | 542 ms
93,548 KB |
testcase_35 | AC | 564 ms
93,284 KB |
testcase_36 | AC | 550 ms
93,556 KB |
testcase_37 | AC | 519 ms
93,348 KB |
testcase_38 | AC | 495 ms
93,464 KB |
testcase_39 | AC | 607 ms
94,276 KB |
ソースコード
class SegmentTree: def segfunc(self,x,y): return min(x,y) def __init__(self,first_list,first_value): n = len(first_list) self.first_value = first_value self.num = 1<<(n-1).bit_length() self.tree = [first_value]*2*self.num for i in range(n): self.tree[self.num+i] = first_list[i] for i in range(self.num-1,0,-1): self.tree[i] = self.segfunc(self.tree[2*i],self.tree[2*i+1]) def update(self,k,x): k += self.num self.tree[k] = x while k>1: self.tree[k>>1] = self.segfunc(self.tree[k],self.tree[k^1]) k >>= 1 def query(self,l,r): res = self.first_value l += self.num; r += self.num while l<r: if l&1: res = self.segfunc(res,self.tree[l]) l += 1 if r&1: res = self.segfunc(res,self.tree[r-1]) l >>= 1; r >>= 1 return res def get(self, k): return self.tree[k+self.num] from bisect import bisect h,w = map(int,input().split()) s = [input() for _ in range(h)] t = [[-1]+[j for j in range(w) if s[i][j]=="#"]+[w] for i in range(h)] dp = SegmentTree([0]*w,w) for i in range(h-2,-1,-1): eq = [w]*w for j in range(w): if s[i][j]=="#": continue k = bisect(t[i],j); l = t[i][k-1]+1; r = t[i][k]-1 wa = -1; ac = w-1 while ac-wa>1: wj = (wa+ac)//2 if dp.query(max(j-wj,l),min(j+wj,r)+1)<=wj: ac = wj else: wa = wj eq[j] = ac dp = SegmentTree(eq,w) for i in range(w): print(dp.get(i))