제출 #1277507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277507		nanaseyuzuki	Snowball (JOI21_ho_t2)	C++20	33 / 100	17 ms	4172 KiB

Main

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 1e5 + 5, inf = 1e18;

int n, q, a[mn], w[mn], prefix[mn], prefix_min[mn], prefix_max[mn], lef[mn], rig[mn];

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) cin >> w[i];

    for(int i = 1; i <= q; i++){
        prefix[i] = prefix[i - 1] + w[i];
        prefix_min[i] = min(prefix_min[i - 1], prefix[i]);
        prefix_max[i] = max(prefix_max[i - 1], prefix[i]);
    }

    a[0] = - inf;
    a[n + 1] = inf;

    for(int i = 1; i <= n; i++){
        int l = 0, r = q, ans1 = -1;

        while(l <= r){
            int mid = (l + r) >> 1;
            if(a[i] + prefix_min[mid] > a[i - 1] + prefix_max[mid]){
                ans1 = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if(prefix[ans1 + 1] < 0) lef[i] = a[i] - a[i - 1] - prefix_max[ans1];
        else lef[i] = prefix_min[ans1] * - 1;

        l = 0, r = q; int ans2 = -1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(a[i] + prefix_max[mid] < a[i + 1] + prefix_min[mid]){
                ans2 = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if(prefix[ans2 + 1] > 0) rig[i] = a[i + 1] - a[i] + prefix_min[ans2];
        else rig[i] = prefix_max[ans2];

        cout << lef[i] + rig[i] << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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