Submission #535702

#TimeUsernameProblemLanguageResultExecution timeMemory
535702sam571128Snowball (JOI21_ho_t2)C++17
33 / 100
2 ms596 KiB
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e3+5;
int arr[N], mn[N], mx[N], ans[N], ask[N];
int now = 0;

signed main(){
    fastio
    int n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> arr[i];
    }

    for(int i = 1;i <= q;i++){
        cin >> ask[i];
        now += ask[i];
        mn[i] = min(mn[i-1],now);
        mx[i] = max(mx[i-1],now);
    }

    ans[1] -= mn[q], ans[n] += mx[q];

    for(int i = 1;i <= n-1;i++){
        int dis = arr[i+1]-arr[i];
        int l = 0, r = q;
        while(l < r){
            int mid = (l+r+1)>>1;
            if(mx[mid]-mn[mid] <= dis) l = mid;
            else r = mid-1;
        }   

        ans[i] += mx[l], ans[i+1] -= mn[l];

        if(l != q){
            if(ask[l+1]>0){
                ans[i] += dis-(mx[l]-mn[l]);
            }else{
                ans[i+1] += dis-(mx[l]-mn[l]);
            }
        }
    }

    for(int i = 1;i <= n;i++){
        cout << ans[i] << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...