結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
10,624 KB
testcase_01 AC 33 ms
10,752 KB
testcase_02 AC 34 ms
10,752 KB
testcase_03 AC 35 ms
10,624 KB
testcase_04 AC 569 ms
19,040 KB
testcase_05 AC 36 ms
10,752 KB
testcase_06 AC 34 ms
10,624 KB
testcase_07 AC 36 ms
10,880 KB
testcase_08 AC 103 ms
12,544 KB
testcase_09 AC 79 ms
11,264 KB
testcase_10 AC 88 ms
11,520 KB
testcase_11 AC 67 ms
10,624 KB
testcase_12 AC 343 ms
11,520 KB
testcase_13 AC 597 ms
21,372 KB
testcase_14 AC 828 ms
32,212 KB
testcase_15 AC 34 ms
10,624 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