提出 #74050072

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
const ll mod = 998244353;

// #include <atcoder/all>
// using mint = atcoder::modint998244353;
// using namespace atcoder;

// binary indexed tree (fenwick tree)
template<typename T>
class bit {
private:
    int sz;
    std::vector<T> dat;

    // O(logN), sum of [0, idx)
    T sum(int idx) {
        T s(0);
        for (int i=idx; i>0; i-=i&-i) s += dat[i-1];
        return s;
    }

public:
    bit(int n) : sz(n), dat(n, T(0)) {}

    // O(logN)
    void add(int idx, T val) {
        assert(0<=idx && idx<sz);
        for (int i=idx+1; i<=sz; i+=i&-i) dat[i-1] += val;
    }

    T get(int idx) {
        return sum(idx, idx+1);
    }

    void set(int idx, T val) {
        add(idx, val-get(idx));
    }

    // O(logN), sum of [l, r)
    T sum(int l, int r) {
        assert(0<=l && l<=r && r<=sz);
        return sum(r)-sum(l);
    }

    // O(logN), return minimum idx where s<=sum(0, idx)
    int lower_bound(T s) {
        assert(0<=s);
        int x = -1, r = 1;
        while (r<sz) r <<= 1;
        for (int len=r; len>0; len>>=1) {
            if (x+len<sz && dat[x+len]<s) {
                s -= dat[x+len];
                x += len;
            }
        }
        return x+1;
    }

    // O(logN), return minimum idx where s<sum(0, idx)
    int upper_bound(T s) {
        assert(0<=s);
        int x = -1, r = 1;
        while (r<sz) r <<= 1;
        for (int len=r; len>0; len>>=1) {
            if (x+len<sz && dat[x+len]<=s) {
                s -= dat[x+len];
                x += len;
            }
        }
        return x+1;
    }

    std::vector<T> vec() {
        std::vector<T> v;
        for (int i=0; i<sz; i++) v.push_back(sum(i, i+1));
        return v;
    }
};

int main() {
    int n,  q;
    cin >> n >> q;

    vector<int> d(n);
    for (int i=0; i<n; i++) cin >> d[i];
    
    vector<int> t(q);
    for (int i=0; i<q; i++) cin >> t[i];
    
    bit<int> ft(n);
    for (int i=0; i<n; i++) {
      ft.add(i, 1);
    }
    
    for (int i=0; i<q; i++) {
      int idx = ft.lower_bound(t[i]);
      if (idx!=n) {
        if (d[idx]==1) {
          ft.add(idx, -1);
        }
        d[idx]--;
      }
      cout << ft.sum(0, n) << endl;
    }
    
    
    return 0;
}

提出情報

ジャッジ結果