1888F - Minimum Array - CodeForces Solution

#include<bits/stdc++.h>

#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define all(x) (x).begin(),(x).end()
#define int long long 
using i64 = long long;
using PII = std::array<int,2>;
void solve(){
    int n;
    std::cin>>n;
    std::vector<int>a(n);
    for(auto&i : a)std::cin>>i;
    a.push_back(0);
    auto b = a;
    for(int i=1;i<n;i++)b[i] = a[i]-a[i-1];
    a.swap(b);
    int q;
    std::cin>>q;
    std::vector<std::array<int,3>>p(q);
    std::set<std::array<int,2>>st;
    
    auto up = [&](int pos,int x){
          if(x==0)return ;
          auto it = st.lower_bound(PII{pos,-(int)1e18});
          if(it==st.end()||(*it)[0]!=pos){
              st.insert(PII{pos,x});
          }else{ 
              auto[p,y]  = *it;
              st.erase(it);
              if(y+x)st.insert({p,y+x});
          } 
    };
    auto ask = [&](){
        auto it = st.begin();
        if(it!=st.end()&&(*it)[1]<0){
            return 1;
        }  
        return 0;
    };
    int ans = -1;
    for(int i=0;i<q;i++){
        auto&[l,r,x] = p[i];
        std::cin>>l>>r>>x;
        up(l,x);
        up(r+1,-x);
        if(ask()){
            ans = i; 
            std::set<PII>().swap(st);
        }
    } 
    for(int i=0;i<=ans;i++){
        auto&[l,r,x]  =p[i];
        l--,r--;
        a[l] += x;
        a[r+1] -=x;
    }
    for(int i=1;i<n;i++)a[i] += a[i-1];
    for(int i=0;i<n;i++)std::cout<<a[i]<<" \n"[i==n-1];
}

signed main(){
	IOS
	int t=1;
	std::cin>>t;
	while(t--)solve();
	return 0;
}