Submission #387534

#	Time	Username	Problem	Language	Result	Execution time	Memory
387534		wildturtle	Snowball (JOI21_ho_t2)	C++17	100 / 100	274 ms	13932 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,A[500005],B[500005],maxx[500005],minn[500005],ans,r,le,ri,mid,idx;
ll gadakveta(ll x,ll y) {
    le=1; ri=m; ans=-1;
    while(le<=ri) {
        mid=(le+ri)/2;
        if(A[x]+maxx[mid]>=A[y]+minn[mid]) { ri=mid-1; ans=mid; }
        else le=mid+1;
    }
    //if(x==5 && y==6) cout<<"("<<ans<<")";
    idx=min(max(A[x]+maxx[ans],A[y]+minn[ans]),max(A[x]+maxx[ans-1],A[y]+minn[ans-1]));
    return idx;
}
int main() {
    cin>>n>>m;
    for(ll i=1;i<=n;i++) {
        cin>>A[i];
    }
    maxx[0]=a; minn[0]=a;
    for(ll i=1;i<=m;i++) {
        cin>>B[i];
        a+=B[i];
        maxx[i]=max(maxx[i-1],a);
        minn[i]=min(minn[i-1],a);
    }
    //cout<<minn[m]<<" "<<maxx[m]<<endl;
    for(ll i=1;i<=n;i++) {
        if(i==1) l=A[i]+minn[m];
        if(i==n) r=A[i]+maxx[m];
        if(i!=1) { if(A[i-1]+maxx[m]<=A[i]+minn[m]) l=A[i]+minn[m]; else l=gadakveta(i-1,i); }
        if(i!=n) { if(A[i]+maxx[m]<=A[i+1]+minn[m]) r=A[i]+maxx[m]; else r=gadakveta(i,i+1); }
        cout/*<<l<<" "<<r<<" "*/<<r-l<<" ";
    }
}

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