結果
問題 | No.1188 レベルX門松列 |
ユーザー | NatsubiSogan |
提出日時 | 2021-11-28 10:18:56 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,403 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 129,188 KB |
最終ジャッジ日時 | 2024-07-01 02:27:02 |
合計ジャッジ時間 | 7,226 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 275 ms
94,476 KB |
testcase_01 | AC | 424 ms
109,604 KB |
testcase_02 | AC | 397 ms
106,300 KB |
testcase_03 | WA | - |
testcase_04 | AC | 420 ms
125,208 KB |
testcase_05 | AC | 64 ms
67,912 KB |
testcase_06 | AC | 217 ms
93,280 KB |
testcase_07 | AC | 413 ms
109,372 KB |
testcase_08 | WA | - |
testcase_09 | AC | 63 ms
69,080 KB |
testcase_10 | AC | 67 ms
69,680 KB |
testcase_11 | AC | 173 ms
80,516 KB |
testcase_12 | WA | - |
testcase_13 | AC | 179 ms
80,892 KB |
testcase_14 | AC | 343 ms
101,496 KB |
testcase_15 | AC | 493 ms
129,188 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 67 ms
69,872 KB |
testcase_19 | AC | 417 ms
115,968 KB |
testcase_20 | AC | 64 ms
68,372 KB |
testcase_21 | AC | 63 ms
68,528 KB |
testcase_22 | WA | - |
testcase_23 | AC | 62 ms
67,960 KB |
ソースコード
import typing class SegmentTree: def __init__( self, lis: list, ele: typing.Any, op: typing.Callable[[typing.Any, typing.Any], typing.Any]) -> None: self.n = len(lis) self.log = (self.n - 1).bit_length() self.size = 1 << self.log self.op = op self.ele = ele self.tree = self._build(lis) def _build(self, lis: list) -> list: res_tree = [self.ele] * (2 * self.size) for i, a in enumerate(lis): res_tree[self.size + i] = a for i in range(1, self.size)[::-1]: res_tree[i] = self.op(res_tree[2 * i], res_tree[2 * i + 1]) return res_tree def __getitem__(self, i: int) -> None: return self.tree[self.size + i] def __setitem__(self, p: int, x: int) -> None: p += self.size self.tree[p] = x for i in range(1, self.log + 1): self.tree[p >> i] = self.op(self.tree[2 * (p >> i)], self.tree[2 * (p >> i) + 1]) def prod(self, l: int, r: int) -> typing.Any: l += self.size r += self.size L = R = self.ele while l < r: if l & 1: L = self.op(L, self.tree[l]) l += 1 if r & 1: r -= 1 R = self.op(self.tree[r], R) l >>= 1 r >>= 1 return self.op(L, R) def all_prod(self) -> typing.Any: return self.tree[1] def max_right(self, l: int, f: typing.Callable[[typing.Any], typing.Any]) -> int: if l == self.n: return self.n l += self.size sm = self.ele while True: while l % 2 == 0: l >>= 1 if not f(self.op(sm, self.tree[l])): while l < self.size: l *= 2 if f(self.op(sm, self.tree[l])): sm = self.op(sm, self.tree[l]) l += 1 return l - self.size sm = self.op(sm, self.tree[l]) l += 1 if (l & -l) == l: return self.n def one_d_coordinate_compression(l: list) -> list: n = len(l) sorted_list = sorted(set(l)) d = {sorted_list[i]: i for i in range(len(sorted_list))} return [d[i] for i in l] n = int(input()) A = list(map(int, input().split())) ST = SegmentTree([0] * (n + 10), 0, max) A = one_d_coordinate_compression(A) def solve(a): l, r = [0] * n, [0] * n for i in range(n): l[i] = max(l[i], ST.prod(0, a[i]) + 1) ST[a[i]] = max(ST[a[i]], l[i]) for i in range(n + 10): ST[i] = 0 for i in range(n)[::-1]: r[i] = max(r[i], ST.prod(0, a[i]) + 1) ST[a[i]] = max(ST[a[i]], r[i]) res = 0 for i in range(n): res = max(res, min(l[i], r[i]) - 1) return res ans = 0 ans = max(ans, solve(A)) A = [-i for i in A] ans = max(ans, solve(A)) print(ans)