Yukicoder059 鉄道の旅

問題概要

$W[i]$を$N$回処理する。
・$W$が正の数の場合は、重さ$|W|$の荷物を詰む。
・$W$が負の数の場合は、重さ$|W|$の荷物を降ろす。
・荷物を積むまえにすでにその荷物の重さ以上の荷物が$K$個以上列車に積まれている場合にはその荷物を積めない。
また、荷物を降ろす場合に指定した重さの荷物が積まれていない場合も考えられる。
この場合は指定された荷物が無いのだから荷物を降ろす必要は無い。
もし指定された重さの荷物があれば必ず1つ降ろす。

最終的に何個の荷物を最終駅まで運ぶことになるだろうか？

$N\leqq10^5$、$K\leqq10^5$、$|W[i]|\leqq10^6$

yukicoder059

解法

BITを高機能なsetっぽく使うあれ。
値$W[i]$以上の個数を高速にcountできればよい。
値が非常に大きいときはBITの内部をmapにするか、さきに座標圧縮してからやると解ける。

計算量:$O(Nlog(MAXW[i]))$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    template<typename type>
    struct BIT0 {
        int N; int nn; vector<type> data;
        BIT0(int n) { N = n + 1; data = vector<type>(n + 1, 0); nn = 1;    while (nn * 2 <= N)nn *= 2; }
        void add(int i, type w) { i++;   for (int x = i; x < N; x += x & -x) { data[x] += w; } }
        type sum(int i) { type ret = 0;   for (int x = i; x > 0; x -= x & -x) { ret += data[x]; }  return ret; }
        type sum(int l, int r) { return sum(r) - sum(l); }
    };
    
    LL N, K;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N >> K;
        VI W(N);
        for (int &w : W) {
            cin >> w;
        }
    
        BIT0<int> bit(1e6 + 6);
        for (int w : W) {
            if (w < 0) {
                if (bit.sum(-w, -w + 1))bit.add(-w, -1);
            }
            else {
                if (bit.sum(w, 1e6 + 6) < K) {
                    bit.add(w, 1);
                }
            }
        }
        ans = bit.sum(1e6 + 6);
        cout << ans << "\n";
    
        return 0;
    }