結果

問題 No.59 鉄道の旅
ユーザー rpy3cpprpy3cpp
提出日時 2015-07-29 01:22:10
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 828 ms / 5,000 ms
コード長 2,136 bytes
コンパイル時間 106 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 32,212 KB
最終ジャッジ日時 2024-12-24 20:39:19
合計ジャッジ時間 3,838 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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