Submission #62294

---

Source Code Expand

#include <iostream>
#include <cassert>

using namespace std;

const int kMaxI = 1 << 18;  // max (N+M) rounded up to the nearest (2^k)

void add(long* bit, int k, long x)
{
    for (; k <= kMaxI; k += k & ~(k - 1)) {
        bit[k] += x;
    }
}

long sum(const long* bit, int k)
{
    long ans = 0;
    for(; k > 0; k -= k & ~(k - 1)) {
        ans += bit[k];
    }
    return ans;
}

int upper(const long* bit, long x)
{
    int k = 0;
    for (int j = kMaxI / 2; j >= 1; j >>= 1) {
        if (x >= bit[k + j]) { k += j; x -= bit[k]; }
    }
    return k;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, h;
    cin >> n >> m >> h;

    static long bit[kMaxI + 1];

    for (int i = 1; i <= n; i++) {
        long ai;
        cin >> ai;
        add(bit, i, ai);
    }
    for (int i = 1; i <= m; i++) {
        string op;
        long arg;
        cin >> op >> arg;
        if (op == "add") {
            add(bit, ++n, arg);
        } else {
            int k = upper(bit, arg - h);

            if (k >= n) {
                cout << "miss\n"; continue;
            }

            long s0 = sum(bit, k), s1 = sum(bit, k + 1);
            if (s1 >= min(sum(bit, n), arg + h)) {
                add(bit, k + 1, s0 - s1);
                cout << "go\n"; continue;
            } else {
                cout << "stop\n"; continue;
            }
        }
    }

    return 0;
}

Submission Info

Judge Result