結果

問題 No.59 鉄道の旅
ユーザー rpy3cpprpy3cpp
提出日時 2015-07-29 01:22:10
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 583 ms / 5,000 ms
コード長 2,136 bytes
コンパイル時間 998 ms
コンパイル使用メモリ 10,788 KB
実行使用メモリ 29,852 KB
最終ジャッジ日時 2023-08-26 05:40:22
合計ジャッジ時間 2,932 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
8,260 KB
testcase_01 AC 16 ms
8,204 KB
testcase_02 AC 15 ms
7,976 KB
testcase_03 AC 14 ms
8,216 KB
testcase_04 AC 384 ms
16,536 KB
testcase_05 AC 16 ms
8,332 KB
testcase_06 AC 15 ms
8,316 KB
testcase_07 AC 17 ms
8,144 KB
testcase_08 AC 66 ms
10,044 KB
testcase_09 AC 47 ms
8,824 KB
testcase_10 AC 55 ms
9,144 KB
testcase_11 AC 38 ms
8,356 KB
testcase_12 AC 239 ms
9,116 KB
testcase_13 AC 422 ms
19,116 KB
testcase_14 AC 583 ms
29,852 KB
testcase_15 AC 16 ms
8,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class RangeCountSegTree(object):
    '''以下の操作をサポートするデータ構造を提供する。
    1) 数値の追加、削減
    2) ある数値の要素がいくつあるかの問合せ
    3) ある数値以上の要素がいくつあるかの問合せ
    数値は、0..size-1 の範囲内とする。
    （飛び飛びの値の場合は、全データをrankにおきかえてから使えばよい。）
    同じ数値を何度でも追加することができる。

    self.data : 子ノードに含まれる個数を格納した segment tree
    '''
    def __init__(self, size):
        self.data = [0] * (2 * size)
        self.size = size
    
    def __getitem__(self, val):
        return self.data[self.size + val]

    def add(self, val):
        '''値 val を持った要素を追加する。
        '''
        pos = self.size + val
        data = self.data
        while pos:
            data[pos] += 1
            pos >>= 1
        
    def sub(self, val):
        pos = self.size + val
        data = self.data
        while pos:
            data[pos] -= 1
            pos >>= 1
        

    def count_more_than_or_equal(self, val):
        data = self.data
        pos = self.size + val
        count = data[pos]
        while pos:
            if not pos & 1:
                count += data[pos+1]
            pos >>= 1
        return count


if __name__ == '__main__':
    N, K = map(int, input().split())
    Ws = []
    Wset = set()
    for n in range(N):
        w = int(input())
        if w > 0:
            Ws.append(w)
            Wset.add(w)
        elif -w in Wset:
            Ws.append(w)
    uniqW = list(Wset)
    uniqW.sort()
    val2idx = {w: i for i, w in enumerate(uniqW)}
    size = 1 << (len(bin(len(uniqW))) - 2)
    seg = RangeCountSegTree(size)
    for w in Ws:
        if w > 0:
            v = val2idx[w]
            if seg.count_more_than_or_equal(v) >= K:
                continue
            seg.add(v)
        else:
            v = val2idx[-w]
            if seg[v] <= 0:
                continue
            seg.sub(v)
    print(seg.count_more_than_or_equal(0))
0