Submission #1160683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160683		stefdasca	Snowball (JOI21_ho_t2)	C++20	100 / 100	71 ms	12872 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, Q;
    cin >> N >> Q;
    vector<ll> X(N);
    for (int i = 0; i < N; i++){
        cin >> X[i];
    }
    // (Positions are given in increasing order; if not, sort(X.begin(), X.end());)
 
    // Read wind data and compute prefix sums.
    vector<ll> W(Q);
    vector<ll> P(Q+1, 0); // P[0] = 0
    for (int i = 0; i < Q; i++){
        cin >> W[i];
        P[i+1] = P[i] + W[i];
    }
    // Precompute the prefix minimum and maximum.
    vector<ll> L(Q+1), R(Q+1);
    L[0] = R[0] = 0;
    for (int i = 1; i <= Q; i++){
        L[i] = min(L[i-1], P[i]);
        R[i] = max(R[i-1], P[i]);
    }
    // The full (isolated) wind–effect range.
    ll full = R[Q] - L[Q];
 
    // For each snowball (if isolated) the effective interval would be:
    // [ X[i] + L[Q],  X[i] + R[Q] ]
    vector<ll> left_bound(N), right_bound(N);
    for (int i = 0; i < N; i++){
        left_bound[i] = X[i] + L[Q];
        right_bound[i] = X[i] + R[Q];
    }
 
    // Helper: binary search for the smallest t (1 ≤ t ≤ Q) such that R[t] – L[t] ≥ gap.
    auto findT = [&](ll gap) -> int {
        int lo = 1, hi = Q, ans = Q;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(R[mid] - L[mid] >= gap){
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    };
 
    // For each adjacent pair of snowballs, “merge” their effective intervals.
    // Let gap = X[i+1] – X[i]. Then find the smallest t such that R[t]-L[t] >= gap.
    // If the wind on day t (i.e. W[t-1]) is nonnegative, set the meeting point M = X[i+1] + L[t];
    // otherwise (if W[t-1] < 0) set M = X[i] + R[t].
    // Then update the right boundary of snowball i and the left boundary of snowball i+1 to M.
    for (int i = 0; i < N - 1; i++){
        ll gap = X[i+1] - X[i];
        int t = findT(gap);
        ll meet;
        if(t >= 1 && W[t-1] >= 0)
            meet = X[i+1] + L[t];
        else
            meet = X[i] + R[t];
        right_bound[i] = min(right_bound[i], meet);
        left_bound[i+1] = max(left_bound[i+1], meet);
    }
 
    // Propagate boundaries so that intervals are contiguous.
    for (int i = 1; i < N; i++){
        left_bound[i] = max(left_bound[i], left_bound[i-1]);
    }
    for (int i = N - 2; i >= 0; i--){
        right_bound[i] = min(right_bound[i], right_bound[i+1]);
    }
 
    // The final weight for each snowball is the length of its effective interval,
    // capped by the full isolated wind range.
    for (int i = 0; i < N; i++){
        ll ans = right_bound[i] - left_bound[i];
        ans = min(ans, full);
        cout << ans << "\n";
    }
 
    return 0;
}

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