Untitled
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