Submission #535703

#	Time	Username	Problem	Language	Result	Execution time	Memory
535703		sam571128	Snowball (JOI21_ho_t2)	C++17	100 / 100	128 ms	15312 KiB

Main

#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 = 2e5+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";
    }
}

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