Submission #709500

#	Time	Username	Problem	Language	Result	Execution time	Memory
709500		sofija6	Snowball (JOI21_ho_t2)	C++14	100 / 100	795 ms	12348 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
ll n,q,x[MAXN],maxx[MAXN],minn[MAXN];
bool Check_1(ll d,ll pos)
{
    ll l=0,r=q,mid,p=0;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (maxx[mid]>=d)
        {
            p=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return (pos==n || x[pos]+d<=x[pos+1]+minn[p]);
}
bool Check_2(ll d,ll pos)
{
    ll l=0,r=q,mid,p=0;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (minn[mid]<=d)
        {
            p=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return (pos==1 || x[pos]+d>=x[pos-1]+maxx[p]);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll a,cur=0;
    cin >> n >> q;
    for (ll i=1;i<=n;i++)
        cin >> x[i];
    for (ll i=1;i<=q;i++)
    {
        cin >> a;
        cur+=a;
        maxx[i]=max(maxx[i-1],cur);
        minn[i]=min(minn[i-1],cur);
    }
    for (ll i=1;i<=n;i++)
    {
        ll L=0,R=0,l=0,r=maxx[q],mid;
        while (l<=r)
        {
            mid=(l+r)/2;
            if (Check_1(mid,i))
            {
                R=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        l=minn[q];
        r=0;
        while (l<=r)
        {
            mid=(l+r)/2;
            if (Check_2(mid,i))
            {
                L=mid;
                r=mid-1;
            }
            else
                l=mid+1;
        }
        cout << R-L << "\n";
    }
    return 0;
}

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