結果

問題 No.1734 Decreasing Elements
ユーザー customfolkcustomfolk
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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)
0