PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: harshit_300
Tester: sky_nik
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums, binary search/two pointers
PROBLEM:
There are N monsters, the i-th at position X_i and has health H_i.
Every second, you can shoot one monster, which reduces its health by 1. Then, every alive monster will move one step closer to you.
You also have a single bomb, which can be placed at the start at some position x and instantly kills all monsters in [x-K, x+K].
Is there a way to kill all the monsters?
EXPLANATION:
First, let’s look at the problem if the bomb wasn’t available to us — so every monster is present, and only one HP can be reduced at a time.
In this scenario, it’s always optimal to shoot at the leftmost alive monster.
So,
- The first monster can be killed if H_1 \leq X_1.
- The second monster can be killed if H_1 + H_2 \leq X_2
- The third monster can be killed if H_1 + H_2 + H_3\leq X_3
\vdots - The i-th monster can be killed if H_1 + H_2 + \ldots + H_i \leq X_i
Let P_i = H_1 + H_2 + \ldots + H_i denote the prefix sum array of H.
Our earlier observation then says that we can kill all the monsters if and only if P_i \leq X_i for every i.
Next, let’s look at what happens when the bomb is available.
To make things slightly easier to deal with, rather than [x-K, x+K], we can pretend the bomb deletes all enemies in [x, x+2K] (essentially rather than fixing the middle, we’re fixing the left end).
Now, clearly the set of monsters deleted by the bomb will form some subarray [l, r].
Using our initial condition, it’s easy to see that for the remaining monsters:
- For i \lt l, nothing really changes: to kill the first i monsters, P_i \leq X_i should hold.
- For i\gt r, we now no longer have to worry about the monsters from l to r.
So, for these indices, we instead want the condition P_i - (H_l + H_{l+1} + \ldots + H_r) \leq X_i to hold.
The first condition is easy to check: for example, precompute whether P_i \leq X_i for every i, then for each prefix you can once again precompute whether the condition holds.
As for the second condition, notice that (H_l + H_{l+1} + \ldots + H_r) is a constant (and in fact equals P_r - P_{l-1}), so what we really want to know is whether P_i - X_i \leq P_r - P_{l-1} for every i \gt r.
For this, note that it’s enough to know the maximum value of P_i - X_i across all i \gt r, since if that satisfies the inequality then everything will. In other words, we only need to know a certain suffix minimum!
So, with appropriate prefix/suffix computations (which take linear time), we are in fact able to figure out in \mathcal{O}(1) whether placing the bomb at a certain range allows us to kill all the monsters.
This only leaves the task of choosing the range [l, r] of monsters that should be deleted.
Here, we simply try all possibilities - notice that if l is fixed, it’s optimal to choose r to be as large as possible, i.e, the largest index such that X_r - X_l \leq 2K.
For a fixed l, finding such an r can be done in \mathcal{O}(\log N) time using binary search; or you can use two-pointers since r increases with l.
It is also possible to solve this task using a segment tree, as can be seen in the tester’s code below.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
int main(){
IOS
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vector<int> a(n+1);
for(int i=1;i<=n;++i){
cin>>a[i];
}
vector<int> h(n+1);
for(int i=1;i<=n;++i){
cin>>h[i];
}
vector<ll> pref(n+2,1e9);
pref[0]=0;
for(int i=1;i<=n;++i){
pref[i]=pref[i-1]+h[i];
}
vector<ll> suff(n+2,-1e9);
suff[n+1]=a[n]+1;
for(int i=n;i>=1;--i){
suff[i]=min((ll)a[i],suff[i+1]-1)-h[i]+1;
}
int chk=0;
for(int i=1;i<=n;++i){
if(pref[i-1]>a[i-1]) break;
auto j=upper_bound(a.begin(),a.end(),a[i]+2*k)-a.begin();
if(pref[i-1]<suff[j]){
chk=1;
}
}
if(chk){
cout<<"Yes"<<'\n';
}else{
cout<<"No"<<'\n';
}
}
return 0;
}
Tester's code (C++)
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_BITOP_HPP
#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
namespace atcoder {
#if __cplusplus >= 201703L
template <class S,
auto op,
auto e,
class F,
auto mapping,
auto composition,
auto id>
struct lazy_segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as F(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"compostiion must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");
#else
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
#endif
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#endif // ATCODER_LAZYSEGTREE_HPP
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
// b[i] = sum(h[j] for j in range(n) if a[j] == i)
// dp[i] = i - sum(b[j] for j in range(i + 1))
// min(dp[i]) >= 0
// remove (a[i], h[i]):
// b[a[i]] -= h[i]
// for j in range(i, n):
// dp[j] += h[i]
// insert (a[i], h[i]):
// b[a[i]] += h[i]
// for j in range(i, n):
// dp[j] -= h[i]
using S = int64_t;
S op(S l, S r) { return min(l, r); }
S e() { return numeric_limits<S>::max(); }
using F = int64_t;
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t; while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), h(n);
for (auto& ai : a) {
cin >> ai;
}
for (auto& hi : h) {
cin >> hi;
}
map<int, int64_t> mp;
for (int i = 0; i < n; ++i) {
mp[a[i]] += h[i];
}
map<int, int64_t> ps = {{0, 0}};
for (const auto& [key, val] : mp) {
ps[key] = prev(ps.end())->second + val;
}
vector<pair<int, int64_t>> ab(ps.cbegin(), ps.cend());
const int sz = ab.size();
map<int, int> idx;
for (int i = 0; i < sz; ++i) {
const auto& [a, _] = ab[i];
idx[a] = i;
}
lazy_segtree<S, op, e, F, mapping, composition, id> dp(sz);
for (int i = 0; i < sz; ++i) {
const auto& [a, b] = ab[i];
dp.set(i, a - b);
}
set<int> events;
for (const auto& [a, b] : ab) {
events.insert(a - k);
events.insert(a + k);
}
bool any = false;
for (const auto x : events) {
if (idx.count(x + k)) {
dp.apply(idx[x + k], sz, mp[x + k]);
}
any |= dp.all_prod() >= 0;
if (idx.count(x - k)) {
dp.apply(idx[x - k], sz, -mp[x - k]);
}
}
cout << (any ? "YES" : "NO") << '\n';
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = list(map(int, input().split()))
sm = 0
pref, suf = [0]*n, [0]*n
for i in range(n):
sm += h[i]
pref[i] = 1 if sm <= a[i] else 0
if i > 0: pref[i] &= pref[i-1]
suf[i] = sm - a[i]
for i in reversed(range(n-1)):
suf[i] = max(suf[i], suf[i+1])
r = 0
ans = 'No'
removed = 0
for l in range(n):
while r < n and a[r] - a[l] <= 2*k:
removed += h[r]
r += 1
good = 1
if l > 0: good &= pref[l-1]
if r < n: good &= suf[r] - removed <= 0
if good: ans = 'Yes'
removed -= h[l]
print(ans)