結果
問題 |
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 |
ソースコード
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)); }