結果
問題 | No.2036 Max Middle |
ユーザー | lilictaka |
提出日時 | 2022-09-16 13:37:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 187 ms / 2,000 ms |
コード長 | 1,456 bytes |
コンパイル時間 | 1,359 ms |
コンパイル使用メモリ | 86,772 KB |
実行使用メモリ | 122,644 KB |
最終ジャッジ日時 | 2023-08-23 07:58:42 |
合計ジャッジ時間 | 5,658 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,048 KB |
testcase_01 | AC | 71 ms
71,300 KB |
testcase_02 | AC | 71 ms
71,284 KB |
testcase_03 | AC | 73 ms
71,292 KB |
testcase_04 | AC | 71 ms
71,384 KB |
testcase_05 | AC | 74 ms
71,356 KB |
testcase_06 | AC | 72 ms
71,256 KB |
testcase_07 | AC | 71 ms
71,048 KB |
testcase_08 | AC | 141 ms
102,608 KB |
testcase_09 | AC | 178 ms
114,248 KB |
testcase_10 | AC | 185 ms
118,044 KB |
testcase_11 | AC | 170 ms
108,040 KB |
testcase_12 | AC | 168 ms
107,200 KB |
testcase_13 | AC | 187 ms
118,012 KB |
testcase_14 | AC | 91 ms
76,932 KB |
testcase_15 | AC | 89 ms
76,700 KB |
testcase_16 | AC | 181 ms
119,944 KB |
testcase_17 | AC | 164 ms
122,644 KB |
testcase_18 | AC | 129 ms
107,248 KB |
testcase_19 | AC | 169 ms
107,528 KB |
testcase_20 | AC | 171 ms
108,152 KB |
ソースコード
class SegmentTree(object): def __init__(self, A, dot, unit): n = 1 << (len(A) - 1).bit_length() tree = [unit] * (2 * n) for i, v in enumerate(A): tree[i + n] = v for i in range(n - 1, 0, -1): tree[i] = dot(tree[i << 1], tree[i << 1 | 1]) self._n = n self._tree = tree self._dot = dot self._unit = unit def __getitem__(self, i): return self._tree[i + self._n] def update(self, i, v): i += self._n self._tree[i] = v while i != 1: i >>= 1 self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1]) def add(self, i, v,ope): self.update(i, ope(self[i],v)) def sum(self, l, r): #これで[l,r)から取り出す。 l += self._n r += self._n l_val = r_val = self._unit while l < r: if l & 1: l_val = self._dot(l_val, self._tree[l]) l += 1 if r & 1: r -= 1 r_val = self._dot(self._tree[r], r_val) l >>= 1 r >>= 1 return self._dot(l_val, r_val) N = int(input()) A = list(map(int,input().split())) B = [] for i in range(N-1): if A[i] < A[i+1]: B.append(1) else: B.append(0) ans = 0 seg = SegmentTree(B,lambda x,y:x+y,0) for i in range(len(B)): if seg[i] == 0: ans += seg.sum(0,i) print(ans)