Submission #1230428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230428		DangKhoizzzz	Snowball (JOI21_ho_t2)	C++20	100 / 100	88 ms	9800 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;


int mn[maxn] , mx[maxn] , n , q , a[maxn] , b[maxn] , psb[maxn];

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) cin >> b[i];
    for(int i = 1; i <= q; i++)
    {
        psb[i] = psb[i-1] + b[i];
        mn[i] = min(mn[i-1] , psb[i]);
        mx[i] = max(mx[i-1] , psb[i]);
    }

    a[n+1] = INF;
    a[0] = -INF;

    for(int i = 1; i <= n; i++)
    {
        int l = 0 , r = q , resL = 0 , resR = 0 , ansL = 0 , ansR = 0;

        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(a[i] - a[i-1] > mx[mid] + -1*mn[mid])
            {
                resL = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }

        if(psb[resL+1] < 0) ansL = (a[i] - a[i-1]) - mx[resL];
        else ansL = mn[resL]*-1;

        l = 0 , r = q;

        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(a[i+1] - a[i] > mx[mid] + -1*mn[mid])
            {
                resR = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }

        if(psb[resR+1] > 0) ansR = (a[i+1] - a[i]) - -1*mn[resR];
        else ansR = mx[resR];

        cout << ansL + ansR << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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