Submission #503481

#	Time	Username	Problem	Language	Result	Execution time	Memory
503481		InternetPerson10	Snowball (JOI21_ho_t2)	C++17	100 / 100	90 ms	16744 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll BIG = 1234567891234567890;

vector<ll> roll_snowballs(vector<ll> snowballs, vector<ll> wind) {
    int n = snowballs.size();
    int q = wind.size();
    ll le = 0, ri = 0; // Pushes to the right/left
    ll curr = 0;
    vector<pair<ll, ll>> gaps(n+1);
    vector<ll> ans(n);
    gaps[0] = {BIG, -1};
    gaps[n] = {BIG, n-1};
    for(int i = 1; i < n; i++) {
        gaps[i] = {snowballs[i] - snowballs[i-1], i-1};
    }
    sort(gaps.begin(), gaps.end());
    int j = 0;
    for(int i = 0; i < q; i++) {
        curr += wind[i];
        if(curr > 0) le = max(le, curr);
        if(curr < 0) ri = max(ri, -curr);
        while(le + ri >= gaps[j].first) {
            ll l = le, r = ri, siz = gaps[j].first;
            if(curr > 0) l = siz - r;
            if(curr < 0) r = siz - l;
            ans[gaps[j].second] += l;
            ans[gaps[j].second+1] += r;
            j++;
        }
    }
    for(; j < n-1; j++) {
        ans[gaps[j].second] += le;
        ans[gaps[j].second+1] += ri;
    }
    ans[0] += ri;
    ans[n-1] += le;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> snowballs(n), wind(q);
    for(int i = 0; i < n; i++) cin >> snowballs[i];
    for(int i = 0; i < q; i++) cin >> wind[i];
    vector<ll> ans = roll_snowballs(snowballs, wind);
    for(ll a : ans) cout << a << '\n';
}

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