結果

問題 No.59 鉄道の旅
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-11 20:00:39
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 38 ms / 5,000 ms
コード長 1,059 bytes
コンパイル時間 4,688 ms
コンパイル使用メモリ 196,900 KB
実行使用メモリ 16,472 KB
最終ジャッジ日時 2025-08-11 20:00:45
合計ジャッジ時間 5,998 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://kmjp.hatenablog.jp/entry/2014/11/10/0900 より
import std;

// BinaryIndexTree
struct BIT(T) {
	int n;	// 配列の要素数(数列の要素数+1)
	T[] bit;	// データの格納先(1-index)。初期値は0
	this(int n)
	{
		this.n = n + 1;
		bit = new T[](this.n);
	}
	// A_i += x
	void add(int i, T x)
	{
		for (int idx = i; idx < n; idx += (idx & -idx))
			bit[idx] += x;
	}
	// A_1からA_iまでの和
	T sum(int i)
	{
		T s = 0;
		for (int idx = i; idx > 0; idx -= (idx & -idx))
			s += bit[idx];
		return s;
	}
	// A_lからA_rまでの和
	T sum(int l, int r)
	{
		return sum(r - 1) - sum(l - 1);
	}
}

void main()
{
	// 入力
	int N, K;
	readln.chomp.formattedRead("%d %d", N, K);
	// 答えの計算と出力
	const NUM = 1 << 20;
	auto bit = BIT!int(NUM);
	auto W = new int[](1_000_001);
	foreach (_; 0 .. N) {
		int x = readln.chomp.to!int;
		if (x > 0) {
			if (bit.sum(x, NUM) < K) {
				bit.add(x, 1);
				W[x]++;
			}
		} else {
			if (W[-x]) {
				W[-x]--;
				bit.add(-x, -1);
			}
		}
	}
	writeln(bit.sum(NUM));
}
0