結果

問題 No.1435 Mmm......
ユーザー H3PO4H3PO4
提出日時 2022-05-19 09:34:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 572 ms / 2,000 ms
コード長 1,455 bytes
コンパイル時間 565 ms
コンパイル使用メモリ 81,780 KB
実行使用メモリ 109,324 KB
最終ジャッジ日時 2023-10-17 17:42:59
合計ジャッジ時間 14,671 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,480 KB
testcase_01 AC 43 ms
55,480 KB
testcase_02 AC 41 ms
55,476 KB
testcase_03 AC 43 ms
55,480 KB
testcase_04 AC 42 ms
55,476 KB
testcase_05 AC 42 ms
55,480 KB
testcase_06 AC 491 ms
97,536 KB
testcase_07 AC 507 ms
100,788 KB
testcase_08 AC 454 ms
107,300 KB
testcase_09 AC 531 ms
103,756 KB
testcase_10 AC 431 ms
100,484 KB
testcase_11 AC 479 ms
100,152 KB
testcase_12 AC 479 ms
97,560 KB
testcase_13 AC 455 ms
97,544 KB
testcase_14 AC 415 ms
90,676 KB
testcase_15 AC 465 ms
107,300 KB
testcase_16 AC 471 ms
100,792 KB
testcase_17 AC 444 ms
92,956 KB
testcase_18 AC 502 ms
107,372 KB
testcase_19 AC 480 ms
97,852 KB
testcase_20 AC 465 ms
103,788 KB
testcase_21 AC 118 ms
109,324 KB
testcase_22 AC 134 ms
107,852 KB
testcase_23 AC 484 ms
107,912 KB
testcase_24 AC 506 ms
107,912 KB
testcase_25 AC 556 ms
107,912 KB
testcase_26 AC 568 ms
107,912 KB
testcase_27 AC 572 ms
107,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq
from collections import Counter

input = sys.stdin.buffer.readline


class CounterWithMin(Counter):
    __slots__ = ["h"]

    def __init__(self, iterable=tuple()):
        super(CounterWithMin, self).__init__(iterable)
        self.h = list(set(iterable))
        heapq.heapify(self.h)

    def add(self, x):
        if x in self:
            self[x] += 1
        else:
            self[x] = 1
            heapq.heappush(self.h, x)

    def remove(self, x):
        if x not in self:
            raise ValueError(f"{x} not in Counter")
        if self[x] == 1:
            del self[x]
        else:
            self[x] -= 1

    def min(self):
        if not super(CounterWithMin, self).__len__():
            raise ValueError
        while self.h and self.h[0] not in self:
            heapq.heappop(self.h)
        return self.h[0]


N = int(input())
A = tuple(map(int, input().split()))

m1 = min(A[:2])
ct_M = CounterWithMin([-A[0], -A[1]])
ct_m2 = CounterWithMin([max(A[:2])])
ans = 1  # (l,r)=(0,1) は必ず条件を満たす
l = 0
for r in range(2, N):
    ar = A[r]
    ct_M.add(-ar)
    if m1 <= ar:
        ct_m2.add(ar)
    else:
        ct_m2.add(m1)
        m1 = ar
    while -ct_M.min() > m1 + ct_m2.min():
        al = A[l]
        if m1 == al:
            m1 = ct_m2.min()
            ct_m2.remove(m1)
        else:
            ct_m2.remove(al)
        ct_M.remove(-al)
        l += 1
    ans += r - l
print(ans)
0