結果
問題 | No.1435 Mmm...... |
ユーザー | NatsubiSogan |
提出日時 | 2021-10-01 11:42:32 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,560 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 87,168 KB |
実行使用メモリ | 139,568 KB |
最終ジャッジ日時 | 2023-09-25 22:36:19 |
合計ジャッジ時間 | 16,283 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
71,508 KB |
testcase_01 | AC | 80 ms
71,108 KB |
testcase_02 | AC | 81 ms
71,220 KB |
testcase_03 | AC | 78 ms
71,312 KB |
testcase_04 | AC | 78 ms
71,544 KB |
testcase_05 | AC | 79 ms
71,224 KB |
testcase_06 | AC | 536 ms
96,332 KB |
testcase_07 | AC | 650 ms
98,832 KB |
testcase_08 | AC | 527 ms
105,248 KB |
testcase_09 | AC | 536 ms
101,860 KB |
testcase_10 | AC | 495 ms
99,076 KB |
testcase_11 | RE | - |
testcase_12 | AC | 498 ms
96,300 KB |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | AC | 530 ms
105,680 KB |
testcase_16 | AC | 518 ms
99,272 KB |
testcase_17 | RE | - |
testcase_18 | AC | 537 ms
105,184 KB |
testcase_19 | AC | 623 ms
96,324 KB |
testcase_20 | AC | 540 ms
102,136 KB |
testcase_21 | AC | 220 ms
139,568 KB |
testcase_22 | AC | 215 ms
116,240 KB |
testcase_23 | RE | - |
testcase_24 | AC | 573 ms
102,236 KB |
testcase_25 | AC | 550 ms
101,968 KB |
testcase_26 | AC | 709 ms
102,340 KB |
testcase_27 | AC | 551 ms
101,936 KB |
ソースコード
class SlidingWindowAggretgation: def __init__(self, op) -> None: self.op = op self.front_stack = [] self.back_stack = [] def __len__(self) -> int: return len(self.front_stack) + len(self.back_stack) def __bool__(self) -> bool: return len(self) > 0 def __str__(self) -> str: data = [x for x, _ in self.front_stack][::-1] + [x for x, _ in self.back_stack] return str(data) def append(self, x) -> None: fx = x if self.back_stack: fx = self.op(self.back_stack[-1][1], x) self.back_stack.append((x, fx)) def popleft(self) -> None: if not self.front_stack: x = fx = self.back_stack.pop()[0] self.front_stack.append((x, fx)) while self.back_stack: x = self.back_stack.pop()[0] fx = self.op(x, fx) self.front_stack.append((x, fx)) self.front_stack.pop() def all_prod(self): res = None if self.front_stack: res = self.front_stack[-1][1] if self.back_stack: if res is None: res = self.back_stack[-1][1] else: res = self.op(res, self.back_stack[-1][1]) return res def op(a, b): m11, m12, M1 = a m21, m22, M2 = b if m11 < m21: n1 = m11 n2 = min(m21, m12) else: n1 = m21 n2 = min(m11, m22) return (n1, n2, max(M1, M2)) n = int(input()) a = list(map(int, input().split())) INF = 10 ** 18 ans = 0 SWAG = SlidingWindowAggretgation(op) ans = 0 r = 0 def ok(r): m1, m2, M = SWAG.all_prod() return max(M, a[r]) <= m1 + min(m2, a[r]) for l in range(n): while l == r or (r < n and ok(r)): SWAG.append((a[r], INF, a[r])) r += 1 ans += r - l - 1 SWAG.popleft() print(ans)