제출 #1277671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277671		shirokito	Snowball (JOI21_ho_t2)	C++20	100 / 100	71 ms	9116 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e5 + 24;
const ll INF = 1e18;

int n, q; ll x[N];
ll w[N]; ll pf_max[N], pf_min[N];
int pos[N];

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

    x[0] = -INF; x[n + 1] = INF;

    for (int i = 1; i <= q; i++) {
        cin >> w[i];
        w[i] += w[i - 1];
    }

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

    for (int i = 1; i < n; i++) {
        for (int l = 0, r = q; l <= r; ) {
            int mid = (l + r) / 2;
            if (x[i] + pf_max[mid] <= x[i + 1] + pf_min[mid]) {
                pos[i] = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        ll res = 0;

        if (i == n || pos[i] == q) res += pf_max[q];
        else res += min(pf_max[pos[i] + 1], x[i + 1] + pf_min[pos[i]] - x[i]);

        if (i == 1 || pos[i - 1] == q) res += -pf_min[q];
        else res += min(-pf_min[pos[i - 1] + 1], x[i] - (x[i - 1] + pf_max[pos[i - 1]]));

        cout << res << '\n';
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}

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