Submission #838905

#	Time	Username	Problem	Language	Result	Execution time	Memory
838905		LeVanThuc	Snowball (JOI21_ho_t2)	C++17	100 / 100	71 ms	13880 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef thuc
    freopen("input.INP","r",stdin);
    freopen("output.OUT","w",stdout);
#endif
}

const ll N=2e5+10,M=998244353;
ll a[N],n,ans[N];
int main()
{
    online();
    vector<pll> vt;
    ll q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i>1) vt.emplace_back(a[i]-a[i-1],i);
    }
    vt.emplace_back(1e18,1);
    vt.emplace_back(1e18,n+1);
    sort(vt.begin(),vt.end(),greater<pll>());
//    for(auto [x,y]:vt) cout<<x<<' '<<y<<'\n';
    ll mx=0,mn=0,cr=0;
    while(q--)
    {
        ll x;
        cin>>x;
        cr+=x;
        if(minimize(mn,cr))
        {
            while(vt.back().fi<=(mx-mn))
            {
                ll k=vt.back().se;
                ans[k-1]+=mx;
                ll z=vt.back().fi-mx;
                ans[k]+=z;
                vt.pop_back();
            }
        }
        if(maximize(mx,cr))
        {
            while(vt.back().fi<=(mx-mn))
            {
                ll k=vt.back().se;
                ans[k]-=mn;
                ll z=vt.back().fi+mn;
                ans[k-1]+=z;
                vt.pop_back();
            }
        }
    }
    while(vt.size())
    {
        ll k=vt.back().se;
        ans[k]-=mn;
        ans[k-1]+=mx;
        vt.pop_back();
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<'\n';
    }
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67