# BULENE - Editorial

Author: Shreyash Bapodia
Tester: Aryan Choudhary, Istvan Nagy
Editorialist: Daanish Mahajan

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:

1. Find the queries required to solve it.
2. 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
#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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi a(n);
for(int i=0;i<n-1;++i)
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> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         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;
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;
lli sumN = 3e5, sumM = 3e5;
while(T--)
{

sumN-=n;sumM-=m;
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();
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){
lazyupd(n, s, e);
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;
}


what is my mistake can you please tell me i am a beginner

#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
int a[n];
int p[m],c[m];
for(int y=0;y<n;y++)
{
cin>>a[y];
}
for(int y=0;y<m;y++)
{
cin>>p[y];
}
for(int y=0;y<m;y++)
{
cin>>c[y];
}
int g=m;
int k=0;
while(g–)
{
int i=0;
while(c[k]–)
{
while(a[i]<=0)
{
i++;
}
a[i]=a[i]-p[k];
i++;

        }
k++;
}
for(int j=0;j<n;j++)
{
if(a[j]>0)
cout<<a[j]<<" ";
else
cout<<0<<" ";
}
cout<<endl;

}
return 0;


}

I suppose you are getting TLE, if yes, then because of two nested while loop. Try considering worst case.

Is there no other way to avoid TLE apart from using fenwick trees ??

I really loved the approach of setter @shreyshbapodia . Really helpful from the perspective of code it was very clean. Loved it. Thanks.

But I have a doubt about understanding the part of the code.
What was intented in this section of code?

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);
}
And in your segment tree v[2*n+1].ss+=v[n].ss; are u storing the lazy updates in ss?

I guess no bro as we have to update the range of queries. Moreover, there are few data structure that is even more advanced than Fenwick or segment tree. Those are treaps u can use them

#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m,i;
cin>>n>>m;
int a[n];
int p[m],c[m];
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<m;i++){
cin>>p[i];
}
for(i=0;i<m;i++){
cin>>c[i];
}
int g=m;
int k=0;
while(g--){
int i=0;
while(c[k]--){

while(i<n && a[i]<=0){  //you miss (i<n) condition due to which it cause segmentation fault for some test case
i++;
}
if(i>=n){  // also this part
break;
}
a[i]=a[i]-p[k];
i++;

}
k++;

}

for(i=0;i<n;i++){
if(a[i]>0)
cout<<a[i]<<" ";
else
cout<<0<<" ";
}
cout<<"\n";

}
}



Although your logic is inefficient because worst-case time complexity is O(m*n). Please see the editorialist’s solution.
Thanks

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{

ll t;
cin >> t;
while (t--)
{
ll int n, m;
cin >> n >> m;
ll int s[n];
ll int p[m];
ll int c[m];
for (ll int i = 0; i < n; i++)
{
cin >> s[i];
}
for (ll int i = 0; i < m; i++)
{
cin >> p[i];
}
for (ll int i = 0; i < m; i++)
{
cin >> c[i];
}

ll int j = 0;
ll int cnt = 0;
ll int k = -1;

while (j < m)
{
k++;

if (cnt < c[j])
{

if(s[k] <= 0)
{
c[j]++;
}
if (k >= n)
{
cnt = 0;
j++;
k = -1;
continue;
}

s[k] -= p[j];
cnt++;
}
else
{

j++;
cnt = 0;
k = -1;
}
}
for (ll int q = 0; q < n; q++)
{
if (s[q] <= 0)
{
s[q] = 0;
}
cout << s[q] << " ";
}
cout << endl;
}
return 0;

}

hey @rough_07,
Congrats on posting your first query!

Although your logic is inefficient because the worst-case time complexity is O(m*n).
So it might give TLE in some test cases.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{

ll t;
cin >> t;
while (t--)
{
ll int n, m;
cin >> n >> m;
ll int s[n];
ll int p[m];
ll int c[m];
for (ll int i = 0; i < n; i++)
{
cin >> s[i];
}
for (ll int i = 0; i < m; i++)
{
cin >> p[i];
}
for (ll int i = 0; i < m; i++)
{
cin >> c[i];
}

ll int j = 0;
ll int cnt = 0;
ll int k = -1;

while (j < m)
{
k++;

if (cnt <  c[j])
{

// if(s[k] <= 0)   this part is irrevelent
//  {
//      c[j]++;
//  }
if (k >= n)
{
cnt = 0;
j++;
k = -1;
continue;
}

if(s[k] > 0){  // you must have to check if( s[k] > 0) first before updating s[k] and cnt.
s[k] -= p[j];
cnt++;
}

}
else
{

j++;
cnt = 0;
k = -1;
}
}
for (ll int q = 0; q < n; q++)
{
if (s[q] <= 0)
{
s[q] = 0;
}
cout << s[q] << " ";
}
cout << endl;
}
return 0;

}