Submission #1332799

#TimeUsernameProblemLanguageResultExecution timeMemory
1332799LuvidiSnowball (JOI21_ho_t2)C++20
100 / 100
66 ms11464 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n,m;
    cin>>n>>m;
    ll a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    ll b[m+1],b1[m+1],b2[m+1],b3[m+1];
    b[0]=b1[0]=b2[0]=b3[0]=0;
    for(int i=1;i<=m;i++){
        cin>>b[i];
        b[i]+=b[i-1];
        b1[i]=min(b1[i-1],b[i]);
        b2[i]=max(b2[i-1],b[i]);
        b3[i]=b2[i]-b1[i];
    }
    ll ans[n];
    memset(ans,0,sizeof(ans));
    ans[0]+=-b1[m];
    ans[n-1]+=b2[m];
    for(int i=0;i+1<n;i++){
        int j=upper_bound(b3,b3+m+1,a[i+1]-a[i])-b3-1;
        ans[i]+=b2[j];
        ans[i+1]-=b1[j];
        if(j<m){
            if(b[j+1]>0)ans[i]+=a[i+1]-a[i]-(b2[j]-b1[j]);
            else ans[i+1]+=a[i+1]-a[i]-(b2[j]-b1[j]);
        }
    }
    for(ll i:ans)cout<<i<<'\n';
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...