結果

問題 No.59 鉄道の旅
ユーザー masa
提出日時 2016-07-29 13:19:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 5,000 ms
コード長 904 bytes
コンパイル時間 683 ms
コンパイル使用メモリ 71,888 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-12-24 22:25:47
合計ジャッジ時間 1,602 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
const int W_MAX = 1000000;
class BIT
{
private:
    int n;
    vector<int> bit;
public:
    BIT();
    BIT(int a) {
        n = a;
        bit.assign(n + 1, 0);
    }
    ~BIT() {
        bit.clear();
    };
    void add(int idx, int val) {
        while (idx <= n) {
            bit[idx] += val;
            idx += idx & -idx;
        }
    }
    int sum(int idx) {
        int ret = 0;
        while (idx > 0) {
            ret += bit[idx];
            idx -= idx & -idx;
        }
        return ret;
    }
    int get(int idx) {
        return sum(idx) - sum(idx - 1);
    }
};
int main() {
    int n, k, w;
    scanf("%d %d", &n, &k);
    BIT bit(W_MAX);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w);
        if (w >= 0) {
            if (bit.sum(W_MAX) - bit.sum(w - 1) < k) {
                bit.add(w, 1);
            }
        } else {
            w = -w;
            if (bit.get(w) > 0) {
                bit.add(w, -1);
            }
        }
    }
    printf("%d\n", bit.sum(W_MAX));
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0