Untitled

 avatar
unknown
c_cpp
a year ago
2.1 kB
12
Indexable
#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
public:
    SegmentTree(int size) : size(size) {
        tree.resize(2 * size, 0);
    }

    void update(int pos) {
        for (tree[pos += size]++; pos > 1; pos >>= 1) {
            tree[pos >> 1] = tree[pos] + tree[pos ^ 1];
        }
    }

    int query(int l, int r) {
        int res = 0;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += tree[l++];
            if (r & 1) res += tree[--r];
        }
        return res;
    }

private:
    int size;
    vector<int> tree;
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> energy(n + 1), layers(n + 1), prefixSum(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> energy[i];
    }

    for (int i = 1; i <= n; ++i) {
        cin >> layers[i];
    }

    for (int i = 1; i <= n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + layers[i];
    }

    vector<int> find(n + 1);
    for (int i = 1; i <= n; ++i) {
        int left = i, right = n, idx = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (prefixSum[mid] - prefixSum[i - 1] <= k) {
                idx = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        find[i] = idx;
    }

    vector<vector<int>> indices(n + 5);
    for (int i = 1; i <= n; ++i) {
        int left = 1, right = i, idx = i + 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (prefixSum[i] - prefixSum[mid - 1] + energy[i] <= k) {
                idx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        indices[idx].push_back(i);
    }

    vector<int> result(n + 1);
    SegmentTree segTree(n + 5);

    for (int i = 1; i <= n; ++i) {
        for (int j : indices[i]) {
            segTree.update(j);
        }
        result[i] = segTree.query(i, find[i]);
        cout << result[i] << endl;
    }
}

int main() {
    
    solve();
    return 0;
}
Editor is loading...
Leave a Comment