結果
問題 | No.59 鉄道の旅 |
ユーザー | kyuna |
提出日時 | 2019-07-27 22:28:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 5,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 581 ms |
コンパイル使用メモリ | 71,168 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-07-02 14:49:16 |
合計ジャッジ時間 | 1,260 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 |
ソースコード
#include <algorithm> #include <iostream> #include <vector> using namespace std; template<typename Abel> struct BIT { const Abel UNITY_SUM = 0; vector<Abel> dat; BIT(int n) : dat(n, UNITY_SUM) { } // [0, n) inline void add(int i, Abel x) { while (i < dat.size()) { dat[i] += x; i |= i + 1; } } inline Abel sum(int i) { // [0, i] Abel res = UNITY_SUM; while (i >= 0) { res += dat[i]; i = (i & (i + 1)) - 1; } return res; } inline Abel sum(int a, int b) { return sum(b - 1) - sum(a - 1); } // [a, b) /* debug */ Abel operator[](int i) { return sum(i, i + 1); } void dump() { for (int i = 0; i < dat.size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; int main() { int n, k; cin >> n >> k; BIT<int> bit(1000001); int cnt = 0; while (n--) { int w; cin >> w; if (w > 0) { if (cnt - bit.sum(w - 1) >= k) continue; cnt++; bit.add(w, 1); } else { w *= -1; if (bit[w] == 0) continue; bit.add(w, -1); cnt--; } } cout << cnt << endl; return 0; }