#include #include #include namespace nono { /// brief : 一点更新 区間取得のsegment tree. template class SegmentTree { using T = M::Value; public: SegmentTree(): SegmentTree(0) {} explicit SegmentTree(int n): SegmentTree(std::vector(n, M::e())) {} explicit SegmentTree(const std::vector& v): n_(int(v.size())) { size_ = std::bit_ceil((unsigned int)(n_)); log_ = std::countr_zero((unsigned int)size_); data_ = std::vector(2 * size_, M::e()); for (int i = 0; i < n_; i++) data_[size_ + i] = v[i]; for (int i = size_ - 1; i >= 1; i--) { update(i); } } /// # set(p, x) /// data[p] <= x /// O(logn) void set(int p, T x) { assert(0 <= p && p < n_); p += size_; data_[p] = x; for (int i = 1; i <= log_; i++) update(p >> i); } /// # get(p) /// return data[p] /// O(logn) T get(int p) const { assert(0 <= p && p < n_); return data_[p + size_]; } /// # prod(l, r) /// return op[for i in [l, r)](data[i]) /// O(logn) T prod(int l, int r) const { assert(0 <= l && l <= r && r <= n_); T sml = M::e(), smr = M::e(); l += size_; r += size_; while (l < r) { if (l & 1) sml = M::op(sml, data_[l++]); if (r & 1) smr = M::op(data_[--r], smr); l >>= 1; r >>= 1; } return M::op(sml, smr); } /// # all_prod() /// O(1) T all_prod() const { return data_[1]; } /// # apply(p, f) /// data[p] <= mapping(f, data[p]) /// O(logn) template int max_right(int l, F f) const { assert(0 <= l && l <= n_); assert(f(M::e())); if (l == n_) return n_; l += size_; T sm = M::e(); do { while (l % 2 == 0) l >>= 1; if (!f(M::op(sm, data_[l]))) { while (l < size_) { l = (2 * l); if (f(M::op(sm, data_[l]))) { sm = M::op(sm, data_[l]); l++; } } return l - size_; } sm = M::op(sm, data_[l]); l++; } while ((l & -l) != l); return n_; } /// # apply(l, r, f) /// [for i in [l, r)](data[i] <= mapping(f, data[i]) /// O(logn) template int min_left(int r, F f) const { assert(0 <= r && r <= n_); assert(f(M::e())); if (r == 0) return 0; r += size_; T sm = M::e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(M::op(data_[r], sm))) { while (r < size_) { r = (2 * r + 1); if (f(M::op(data_[r], sm))) { sm = M::op(data_[r], sm); r--; } } return r + 1 - size_; } sm = M::op(data_[r], sm); } while ((r & -r) != r); return 0; } private: int n_, size_, log_; std::vector data_; void update(int k) { data_[k] = M::op(data_[2 * k], data_[2 * k + 1]); } }; } // namespace nono #include #include #include #include namespace nono { namespace monoid { struct MonoidTemplate { struct Value {}; static Value op(Value lhs, Value rhs); static Value e(); }; /// # Min template struct Min { using Value = T; static Value op(Value lhs, Value rhs) { return std::min(lhs, rhs); } static Value e() { return std::numeric_limits::max(); } }; /// # Max template struct Max { using Value = T; static Value op(Value lhs, Value rhs) { return std::max(lhs, rhs); } static Value e() { return std::numeric_limits::min(); } }; /// # MinMax template struct MinMax { struct Value { Value(): min(std::numeric_limits::max()), max(std::numeric_limits::min()) {} Value(T val): min(val), max(val) {} Value(T min, T max): min(min), max(max) {} T min, max; }; static Value op(Value lhs, Value rhs) { return Value{std::min(lhs.min, rhs.min), std::max(lhs.max, rhs.max)}; } static Value e() { return Value{}; } }; /// # Add template struct Add { using Value = T; static Value op(Value lhs, Value rhs) { return lhs + rhs; } static Value e() { return static_cast(0); } }; /// # Mul template struct Mul { using Value = T; static Value op(Value lhs, Value rhs) { return lhs * rhs; } static Value e() { return static_cast(1); } }; /// # Composite /// (ax + b) 関数の合成 template struct Composite { struct Value { Value(T a = 1, T b = 0): a(a), b(b) {} T a; T b; T eval(T x) { return a * x + b; } }; static Value op(Value lhs, Value rhs) { return {lhs.a * rhs.a, rhs.a * lhs.b + rhs.b}; } static Value e() { return Value{}; } }; /// # MinIndex /// (a, i), (b, j) /// [1] if a <= b: /// return (a, i) /// [2] else /// return (b, j) /// 同じなら左側 template struct MinIndex { struct Value { Value(T value, int index): value(value), index(index) {} T value; int index; }; static Value op(Value lhs, Value rhs) { return (lhs.value <= rhs.value ? lhs : rhs); } static Value e() { return {std::numeric_limits::max(), -1}; } }; template struct MaxIndex { struct Value { T value; int index; }; static Value op(Value lhs, Value rhs) { return (lhs.value >= rhs.value ? lhs : rhs); } static Value e() { return {std::numeric_limits::min(), -1}; } }; /// # Rev template struct Rev { using T = M::Value; struct Value { Value(): ord(M::e()), rev(M::e()) {} Value(T v_): ord(v_), rev(v_) {} T ord, rev; }; static Value op(Value lhs, Value rhs) { lhs.ord = M::op(lhs.ord, rhs.ord); lhs.rev = M::op(rhs.rev, lhs.rev); return lhs; } static Value e() { return Value{}; } }; /// # Gcd template struct Gcd { using Value = T; static Value op(Value lhs, Value rhs) { return std::gcd(lhs, rhs); } static Value e() { return Value{0}; } }; /// # MaxSubSeq /// max[for r in [0, n), for r in [l + 1, n]](sum[for i in [l, r)](data[i])) template struct MaxSubSeq { struct Value { Value(T v = 0): val(std::max(T{0}, v)), prefix(std::min(T{0}, v)), suffix(std::max(T{0}, v)), sum(v) {} T max_subseq_sum() const { return val; } T val, prefix, suffix, sum; }; static Value op(Value lhs, Value rhs) { Value result{}; result.prefix = std::min(lhs.prefix, lhs.sum + rhs.prefix); result.suffix = std::max(lhs.suffix, lhs.sum + rhs.suffix); result.sum = lhs.sum + rhs.sum; result.val = std::max({lhs.val, rhs.val, (rhs.suffix + lhs.sum) - (lhs.prefix)}); return result; } static Value e() { return Value{}; } }; } // namespace monoid } // namespace nono #include using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; template using MaxHeap = std::priority_queue; template using MinHeap = std::priority_queue, greater>; #define rep2(i, n) for (ll i = 0; i < (n); i++) #define rep3(i, l, r) for (ll i = (l); i < (r); i++) #define rrep2(i, n) for (ll i = n; i-- > 0;) #define rrep3(i, r, l) for (ll i = (r); i-- > (l);) #define overload(a, b, c, d, ...) d #define rep(...) overload(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rrep(...) overload(__VA_ARGS__, rrep3, rrep2)(__VA_ARGS__) #define all(x) begin(x), end(x) bool chmin(auto& lhs, auto rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; } bool chmax(auto& lhs, auto rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; } struct IOIO { IOIO() { std::cin.tie(0)->sync_with_stdio(0); } } ioio; void solve() { using M = nono::monoid::MinIndex>; using Segtree = nono::SegmentTree; int n; ll h; int t; cin >> n >> h >> t; vector a(n); rep(i, n) cin >> a[i]; vector c(n); Segtree segtree(n); rep(i, n) { ll num = (h + a[i] - 1) / a[i]; segtree.set(i, {pair{num, -a[i] * num}, (int)i}); } ll offset = 0; rep(i, t) { auto res = segtree.all_prod(); c[res.index]++; offset = res.value.first; res.value.first = offset + ((h + a[res.index] - 1) / a[res.index]); segtree.set(res.index, res); } rep(i, n) cout << c[i] << " \n"[i + 1 == n]; } int main() { int t = 1; // cin >> t; while (t--) solve(); }