Submission #1266350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266350		hahahoang132	Snowball (JOI21_ho_t2)	C++20	100 / 100	195 ms	98524 KiB

Main

//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/5;
const ll mod = 998244353;
#define bit(x,y) ((x >> y) & 1LL)

ll a[N],b[N],ans[N],l[N],r[N];
vector<ll> qr[N];
vector<ll> haha[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,q;
    cin >> n >> q;
    ll i,j;
    a[1] = -inf;
    a[n + 2] = inf;
    for(i = 2;i <= n + 1;i++)
    {
        cin >> a[i];
    }
    for(i = 1;i <= q;i++) cin >> b[i];
    for(i = 1;i <= n + 1;i++)
    {
        l[i] = 0;
        r[i] = q;
    }
    while(true)
    {
        ll cr = 0;
        for(i = 1;i <= n + 1;i++)
        {
            if(l[i] == r[i]) continue;
            cr = 1;
            ll mid = (l[i] + r[i] + 1) / 2;
            qr[mid].push_back(i);
        }
        if(cr == 0) break;
        ll cur = 0;
        ll minv = 0,maxv = 0;
        for(i = 1;i <= q;i++)
        {
            cur += b[i];
            minv = min(minv,cur);
            maxv = max(maxv,cur);
            while(qr[i].size() > 0)
            {
                ll id = qr[i].back();
                qr[i].pop_back();
                if(a[id] + maxv <= a[id + 1] + minv)
                {
                    l[id] = i;
                }else r[id] = i - 1;
            }
        }
    }
    for(i = 1;i <= n + 1;i++)
    {
        haha[l[i] + 1].push_back(i);
    }
    ll minv = 0,maxv = 0,cur = 0;
    for(i = 1;i <= q + 1;i++)
    {
        while(haha[i].size() > 0)
        {
            ll id = haha[i].back();
            haha[i].pop_back();
            if(b[i] >= 0)
            {
                ans[id] += maxv + min(a[id + 1] + minv - (a[id] + maxv),b[i]);
                ans[id + 1] += -minv;
            }else
            {
                ans[id] += maxv;
                ans[id + 1] += -minv + min(a[id + 1] + minv - (a[id] + maxv),-b[i]);
            }
        }
        cur += b[i];
        minv = min(minv,cur);
        maxv = max(maxv,cur);
    }
    for(i = 2;i <= n + 1;i++) cout << ans[i] << "\n";
}

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