結果
問題 | No.1734 Decreasing Elements |
ユーザー | customfolk |
提出日時 | 2021-11-12 20:27:27 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 1,215 ms / 3,000 ms |
コード長 | 3,094 bytes |
コンパイル時間 | 1,575 ms |
コンパイル使用メモリ | 86,716 KB |
実行使用メモリ | 142,116 KB |
最終ジャッジ日時 | 2023-08-16 20:01:40 |
合計ジャッジ時間 | 27,269 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 110 ms
77,936 KB |
testcase_01 | AC | 114 ms
77,904 KB |
testcase_02 | AC | 116 ms
78,804 KB |
testcase_03 | AC | 113 ms
77,956 KB |
testcase_04 | AC | 113 ms
77,680 KB |
testcase_05 | AC | 115 ms
77,924 KB |
testcase_06 | AC | 116 ms
78,740 KB |
testcase_07 | AC | 990 ms
124,280 KB |
testcase_08 | AC | 1,117 ms
126,664 KB |
testcase_09 | AC | 1,044 ms
125,756 KB |
testcase_10 | AC | 1,068 ms
129,796 KB |
testcase_11 | AC | 1,024 ms
132,084 KB |
testcase_12 | AC | 705 ms
111,192 KB |
testcase_13 | AC | 1,000 ms
125,128 KB |
testcase_14 | AC | 1,186 ms
141,792 KB |
testcase_15 | AC | 1,103 ms
130,000 KB |
testcase_16 | AC | 1,141 ms
142,116 KB |
testcase_17 | AC | 1,157 ms
138,208 KB |
testcase_18 | AC | 1,151 ms
138,664 KB |
testcase_19 | AC | 1,111 ms
121,756 KB |
testcase_20 | AC | 1,155 ms
122,724 KB |
testcase_21 | AC | 936 ms
114,656 KB |
testcase_22 | AC | 1,076 ms
123,000 KB |
testcase_23 | AC | 1,069 ms
123,328 KB |
testcase_24 | AC | 987 ms
124,264 KB |
testcase_25 | AC | 1,215 ms
131,248 KB |
testcase_26 | AC | 1,138 ms
131,504 KB |
ソースコード
from collections import defaultdict, deque, Counter from heapq import heapify, heappop, heappush import math from copy import deepcopy from itertools import combinations, permutations, product, combinations_with_replacement from bisect import bisect_left, bisect_right import sys def input(): return sys.stdin.readline().rstrip() def getN(): return int(input()) def getNM(): return map(int, input().split()) def getList(): return list(map(int, input().split())) def getListGraph(): return list(map(lambda x:int(x) - 1, input().split())) def getArray(intn): return [int(input()) for i in range(intn)] mod = 10 ** 9 + 7 MOD = 998244353 sys.setrecursionlimit(10000000) inf = float('inf') eps = 10 ** (-15) dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] ############# # Main Code # ############# class BIT: def __init__(self, N): self.N = N self.bit = [0] * (N + 1) self.b = 1 << N.bit_length() - 1 def add(self, a, w): x = a while(x <= self.N): self.bit[x] += w x += x & -x # [0, a)の合計 def get(self, a): ret, x = 0, a - 1 while(x > 0): ret += self.bit[x] x -= x & -x return ret # [l, r)の合計 def cum(self, l, r): return self.get(r) - self.get(l) # 最も近くにあるフラグの立っている場所を探す def lowerbound(self,w): if w <= 0: return 0 x = 0 k = self.b while k > 0: if x + k <= self.N and self.bit[x + k] < w: w -= self.bit[x + k] x += k k //= 2 return x + 1 """ Ajはもちろん自身を引いて0になる 右にある自分より大きいものから引く 何回目で自身が消えているか スキップする回数を引く 左から順に 自身より小さい数があればそれを引く 自身が消えているか のみ見る 例えば1 1 1 2 2 2 6 の6は消えない gcdの問題? [0, 1, 2, 3, 4, 5, 6, 7, 8...]とする 4がくる [0, 1, 2, 3, 0, 1, 2, 3, 4...] 3がくる [0 ,1, 2, 0, 0, 1, 2, 0, 1...] 現在の0の場所を起点に次の0との間隔がKより大きいものについて新しく0を立てる 最初(次の場所との間隔10**6, 0) 4がくる(inf, 4), (4, 0) # 間隔が大きい順に 3がくる(inf, 7), (3, 4), (1, 3), (3, 0) (元の間隔, Ai + K)、(K, Ai) Aiの値も変動する aは最後の0の位置からいくつめか """ N = getN() A = getList() q = [[-(2 * 10 ** 5 + 7), 0]] # どこに0が立っているか bit = BIT(2 * 10 ** 5 + 7) ans = 0 for a in A: # 最後の0の位置を探索 現在のaの値は k = a - bit.lowerbound(bit.get(a + 1)) if k == 0: continue # countする ans += 1 psu = [] # aより間隔が広いものを引っ張る while q and -q[0][0] > k: psu.append(heappop(q)) for ran, now in psu: # 間隔が詰まる bit.add(now + k, 1) heappush(q, [ran + k, now + k]) heappush(q, [-k, now]) print(ans)