結果

問題 No.1734 Decreasing Elements
コンテスト
ユーザー customfolk
提出日時 2021-11-12 20:27:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 980 ms / 3,000 ms
コード長 3,094 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 139,396 KB
最終ジャッジ日時 2024-11-25 09:56:57
合計ジャッジ時間 19,209 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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