結果

問題 No.1734 Decreasing Elements
ユーザー customfolkcustomfolk
提出日時 2021-11-12 20:27:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,028 ms / 3,000 ms
コード長 3,094 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 139,412 KB
最終ジャッジ日時 2024-05-04 03:26:44
合計ジャッジ時間 20,462 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
63,932 KB
testcase_01 AC 47 ms
64,112 KB
testcase_02 AC 51 ms
65,844 KB
testcase_03 AC 48 ms
63,796 KB
testcase_04 AC 46 ms
63,556 KB
testcase_05 AC 46 ms
62,924 KB
testcase_06 AC 48 ms
65,108 KB
testcase_07 AC 863 ms
121,852 KB
testcase_08 AC 830 ms
126,108 KB
testcase_09 AC 852 ms
123,284 KB
testcase_10 AC 861 ms
126,880 KB
testcase_11 AC 871 ms
129,852 KB
testcase_12 AC 587 ms
109,528 KB
testcase_13 AC 853 ms
123,328 KB
testcase_14 AC 987 ms
139,412 KB
testcase_15 AC 934 ms
128,004 KB
testcase_16 AC 974 ms
138,208 KB
testcase_17 AC 987 ms
134,128 KB
testcase_18 AC 1,004 ms
137,212 KB
testcase_19 AC 948 ms
119,296 KB
testcase_20 AC 996 ms
120,204 KB
testcase_21 AC 779 ms
111,336 KB
testcase_22 AC 914 ms
121,348 KB
testcase_23 AC 927 ms
121,732 KB
testcase_24 AC 871 ms
122,048 KB
testcase_25 AC 1,028 ms
129,912 KB
testcase_26 AC 952 ms
129,768 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