Submission #1175617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175617		igofan	Snowball (JOI21_ho_t2)	C++20	100 / 100	56 ms	8372 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    vector<int> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    vector<pair<int, int>> dis;
    for (int i = 1; i < n; i++) {
        dis.push_back({x[i] - x[i - 1], i});
    }
    sort(dis.begin(), dis.end());
    vector<int> ans(n, 0);
    int mxR = 0, mxL = 0;
    int cur = 0; int idx = 0;    
    while(q--) {
        int w; cin >> w;
        cur += w;
        if (cur > mxR) {
            int total = cur + mxL;
            while(idx<dis.size() && dis[idx].first <= total) {
                ans[dis[idx].second-1]+=dis[idx].first-mxL;
                ans[dis[idx].second]+=mxL;
                idx++;
            }
            mxR = cur;
        } else if (-cur > mxL) {
            int total = -cur + mxR;
            while(idx<dis.size() && dis[idx].first <= total) {
                ans[dis[idx].second]+=dis[idx].first-mxR;
                ans[dis[idx].second-1]+=mxR;
                idx++;
            }
            mxL = -cur;
        }
    }
    while (idx < dis.size()) {
        ans[dis[idx].second-1] += mxR;
        ans[dis[idx].second] += mxL;
        idx++;
    }
    ans[0] += mxL; ans[n-1] += mxR;
    for(int i=0; i<n; i++) cout << ans[i] << "\n";
    return 0;
}

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