PROBLEM LINK:
Practice
Div-4 Contest
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author: Shreyash Bapodia
Tester: Aryan Choudhary, Istvan Nagy
Editorialist: Daanish Mahajan
DIFFICULTY:
Easy - Medium
PREREQUISITES:
Lazy propagation, segment tree / fenwick tree
PROBLEM:
There are N enemies standing from left to right with strengths S_1, S_2, \ldots, S_N.
M bullets are to be fired from the left side such that only one bullet is fired at a time. The i^{th} bullet (1 \le i \le M) has power P_i and capacity C_i.
This means that the i^{th} bullet affects the first C_i alive enemies from the left side and decreases the strength of each of those C_i enemies by P_i.
Once an enemy’s strength becomes less than or equal to 0, the enemy dies and its strength becomes 0.
Find the strength of all the enemies after all M bullets are fired.
EXPLANATION:
To approach any data structure problem, follow the two steps:
- Find the queries required to solve it.
- Use the appropriate data structure to answer every query.
We can approach this problem in two ways:
Way 1:
- Query 1: Finding the location of C_{i}^{th} alive enemy starting from the left - Solve it using a Fenwick array and doing binary search on it in \mathcal {O}(\log N) or use segment tree with range sum for doing the same in same complexity. Total time for all queries will be \mathcal {O}(M \log N).
- Query 2: Reducing the power of the first C_i alive enemies by P_i - Solve it using lazy propagation over the segment tree in \mathcal {O}(\log N). Total time for all queries will be \mathcal {O}(M \log N).
- Query 3: Finding the enemies whose energy has turned \le 0 and thereby updating the fenwick array used to answer query 1 accordingly - This can be done by having a range minimum segment tree to answer query 2 and going only into those nodes where the minimum value \le 0 after the update. The important observation here is that we only end up reaching \mathcal {O}(N) leaves, therefore total time will be \mathcal {O}(N \log N). Make sure to update the strength of the enemy which has been eliminated to
LLONG_MAX.
Way 2: (Setter's approach)
We will calculate the final strength of an enemy iteratively from left to right. Bullet will hit an enemy until its strength is greater than 0.
Let’s say total x bullets hit an enemy i. Therefore the sum of power of all x bullets should be \ge S_i.
We can find this x (using segment tree or fenwick tree) in the power array P.
We then decrease the count of all x bullets by one in the count array C.
If at any moment, count of any bullet becomes zero (we can find this using range minimum query) we remove this bullet or simply make its power zero.
Like this we can calculate the strength of all the enemies.
COMPLEXITY ANALYSIS:
\mathcal {O}((N + M) \log N) for first and \mathcal {O}((N + M) \log M) for second approach.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1000000007;
const ll INF = (ll)1e18;
const ll MAXN = 1000006;
ll po(ll x, ll n){
ll ans=1;
while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2;}
return ans;
}
struct fentree{
vector<ll> v;
int _n;
fentree(int n){
v.assign(n+5,0);
_n = n+5;
}
void upd(int pos, ll val){
while(pos<_n){
v[pos]+=val;
pos|=(pos+1);
}
}
ll qr(int pos){
ll ret = 0;
while(pos>=0){
ret += v[pos];
pos&=(pos+1);
pos--;
}
return ret;
}
int bitSearch(ll sum){
int ret = -1;
rev(i, 21){
if(ret+(1<<i)>=_n) continue;
if(v[ret+(1<<i)]>=sum) continue;
else{
ret += (1<<i);
sum -= v[ret];
}
}
return ret+1;
}
};
struct segtree{
vector<pair<int,int> > v;
vector<int> id;
int _n;
segtree(int n){
v.resize(4*n+5);
id.resize(4*n+5);
_n = n;
}
void relax(int n){
if(2*n+1<v.size()){
v[2*n+1].ss+=v[n].ss;
v[2*n+1].ff+=v[n].ss;
}
if(2*n+2<v.size()){
v[2*n+2].ss+=v[n].ss;
v[2*n+2].ff+=v[n].ss;
}
v[n].ss=0;
}
void build(int n, int tl, int tr, vector<int>&cap){
if(tl==tr){
v[n] = mp(cap[tl],0);
id[n] = tl;
return;
}
int m = (tl+tr)>>1;
build(2*n+1, tl, m, cap);
build(2*n+2, m+1, tr, cap);
v[n].ff = min(v[2*n+1].ff, v[2*n+2].ff);
if(v[n].ff==v[2*n+1].ff) id[n]=id[2*n+1];
else id[n]=id[2*n+2];
}
void upd1(int n, int tl, int tr, int pos){
relax(n);
if(tl==tr){
v[n] = mp(1e9,0);
return;
}
int m = (tl+tr)>>1;
if(pos<=m) upd1(2*n+1, tl, m, pos);
else upd1(2*n+2, m+1, tr, pos);
v[n].ff = min(v[2*n+1].ff, v[2*n+2].ff);
if(v[n].ff==v[2*n+1].ff) id[n]=id[2*n+1];
else id[n]=id[2*n+2];
}
void upd2(int n, int tl, int tr, int l, int r){
if(tl>r || tr<l) return;
if(l<=tl && tr<=r){
v[n].ss--;
v[n].ff--;
return;
}
relax(n);
int m = (tl+tr)>>1;
upd2(2*n+1, tl, m, l, r);
upd2(2*n+2, m+1, tr, l, r);
v[n].ff = min(v[2*n+1].ff, v[2*n+2].ff);
if(v[n].ff==v[2*n+1].ff) id[n]=id[2*n+1];
else id[n]=id[2*n+2];
}
pair<int,int> find_min(int n, int tl, int tr, int l, int r){
if(tl>r || tr<l) return mp(2e9,-1);
if(l<=tl && tr<=r) return mp(v[n].ff, id[n]);
relax(n);
int m = (tl+tr)>>1;
auto a = find_min(2*n+1, tl, m, l, r);
auto b = find_min(2*n+2, m+1, tr, l, r);
if(a.ff<=b.ff) return a;
return b;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("11.in", "r" , stdin);
freopen("11.out", "w" , stdout);
#endif
int T=1;
cin >> T;
while(T--){
int n,m;
cin>>n>>m;
ll str[n];
rep(i,n) cin>>str[i];
ll pow[m];
rep(i,m) cin>>pow[i];
vector<int> cap(m);
rep(i,m) cin>>cap[i];
struct fentree ft(m);
rep(i,m) ft.upd(i, pow[i]);
struct segtree st(m);
st.build(0, 0, m-1, cap);
ll tot_pow = 0;
for(auto h:pow) tot_pow+=h;
rep(i,n){
int r;
int ans = str[i];
if(tot_pow<=str[i]){
r=m-1;
ans-=tot_pow;
}
else{
r=ft.bitSearch(str[i]);
ans = 0;
}
st.upd2(0, 0, m-1, 0, r);
auto z = st.find_min(0, 0, m-1, 0, r);
while(z.ff==0){
tot_pow-=pow[z.ss];
ft.upd(z.ss, -pow[z.ss]);
st.upd1(0, 0, m-1, z.ss);
z = st.find_min(0, 0, m-1, 0, r);
}
cout<<ans<<" ";
}
cout<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
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())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
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
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
bool isBinaryString(const string s){
for(auto x:s){
if('0'<=x&&x<='1')
continue;
return false;
}
return true;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
struct S {
ii c;
lli sum;
};
struct F {
lli used;
};
S op(S l, S r) { return S{min(l.c,r.c), l.sum + r.sum}; }
S e() { return S{{INF,-1}, 0}; }
S mapping(F l, S r) { return S{{r.c.X+l.used,r.c.Y}, r.sum}; }
F composition(F l, F r) { return F{l.used+r.used}; }
F id() { return F{0}; }
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
lli T,n,m;
T=readIntLn(1,1e3);
lli sumN = 3e5, sumM = 3e5;
while(T--)
{
n=readIntSp(1,sumN);
m=readIntLn(1,sumM);
sumN-=n;sumM-=m;
const auto s=readVectorInt(n,1,1e9);
const auto p=readVectorInt(m,1,1e9);
const auto c=readVectorInt(m,1,1e9);
dbg(s,p,c);
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(m+2);
for(lli i=1;i<=m;i++){
const lli pi=p[i-1];
const ii ci={c[i-1],i};
seg.set(i,S{ci,pi});
}
seg.set(m+1,S{{INF,m+1},INF});
for(auto start:s){
auto G = [&](const S l)->bool{
return l.sum<start;
};
const lli r = seg.max_right(0,G);
dbg(start,m,r);
if(r==m+1)
cout<<start-seg.prod(0,m+1).sum<<" ";
else
cout<<0<<" ";
seg.apply(0,r+1,F{-1});
while(true){
const auto g=seg.all_prod();
dbg(g.c.X,g.c.Y,g.sum);
if(g.c.X>0)
break;
dbg("zero",g.c.Y);
seg.set(g.c.Y,S{{INF,g.c.Y},0});
}
}
cout<<endl;
} aryanc403();
readEOF();
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int maxs = 3e5 + 10, maxb = 20;
const ll maxv = 1e18;
ll seg[4 * maxs], lazy[4 * maxs];
ll s[maxs], p[maxs], ps[maxs];
int f[maxs];
int N, M;
void upd(int x, int v){
while(x <= N){
f[x] += v;
x += x & -x;
}
}
int search(int v)
{
int sum = 0;
int pos = 0;
for(int i = maxb; i >= 0; i--)
{
if(pos + (1 << i) <= N and sum + f[pos + (1 << i)] <= v)
{
sum += f[pos + (1 << i)];
pos += (1 << i);
}
}
return pos;
}
void lazyupd(int n, int s, int e){
if(lazy[n] == 0)return;
seg[n] += lazy[n];
if(s != e){
lazy[2 * n + 1] += lazy[n];
lazy[2 * n + 2] += lazy[n];
}
lazy[n] = 0;
if(seg[n] <= 0){
if(s == e){
seg[n] = maxv;
upd(s, -1);
}else{
int m = (s + e) / 2;
lazyupd(2 * n + 1, s, m);
lazyupd(2 * n + 2, m + 1, e);
seg[n] = min(seg[2 * n + 1], seg[2 * n + 2]);
}
}
}
void upd(int n, int s, int e, int l, int r, ll add, int t){
lazyupd(n, s, e);
if(l > e || r < s)return;
if(s >= l && e <= r){
if(t){
lazy[n] += add;
lazyupd(n, s, e);
}else seg[n] = add;
return;
}
int m = (s + e) / 2;
upd(2 * n + 1, s, m, l, r, add, t);
upd(2 * n + 2, m + 1, e, l, r, add, t);
seg[n] = min(seg[2 * n + 1], seg[2 * n + 2]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while(t--){
cin >> N >> M;
for(int i = 0; i <= 4 * N; i++){
lazy[i] = 0; seg[i] = maxv;
}
for(int i = 0; i <= N + 1; i++){
f[i] = 0; ps[i] = 0;
}
for(int i = 1; i <= N; i++){
cin >> s[i];
upd(0, 1, N, i, i, s[i], 0);
upd(i, 1);
}
ll total = 0;
for(int i = 1; i <= M; i++){
cin >> p[i];
total += p[i];
}
int cap;
for(int i = 1; i <= M; i++){
cin >> cap;
int pos = search(cap);
ps[pos + 1] += -p[i];
upd(0, 1, N, 1, pos, -p[i], 1);
}
for(int i = 1; i <= N; i++){
total += ps[i];
cout << max(0LL, s[i] - total) << " \n"[i == N];
}
}
return 0;
}