제출 #1204832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204832		aquasocute	Snowball (JOI21_ho_t2)	C++20	0 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2000005;      // ← bump this up by a few
ll n, q, a[MAXN], ans[MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 1) Build the prefix‐sum‐of‐nonzeros array
    vector<ll> megu;
    megu.reserve(q);
    while(q--){
        ll x; 
        cin >> x;
        if(x == 0) continue;
        if(megu.empty()) megu.push_back(x);
        else            megu.push_back(megu.back() + x);
    }

    // 2) Extract only the “record” maxima (positive) and minima (negative)
    vector<ll> aquaa;
    aquaa.reserve(megu.size());
    ll bestPos = 0, bestNeg = 0;
    for(ll s : megu){
        if(s > 0 && s > bestPos){
            aquaa.push_back(s);
            bestPos = s;
        }
        else if(s < 0 && llabs(s) > bestNeg){
            aquaa.push_back(s);
            bestNeg = llabs(s);
        }
    }

    // If there was never a sign‐change, we only have one “record”:
    if(aquaa.size() <= 1){
        // the only contributions are from the last positive record (bestPos)
        // and the last negative record (bestNeg), which go to ans[n] and ans[1].
        ans[1] = bestNeg;
        ans[n] = bestPos;
        for(int i = 1; i <= n; i++){
            cout << ans[i] << "\n";
        }
        return 0;
    }

    // 3) Keep only the points at which the prefix‐sum flips sign
    vector<ll> aqua;
    aqua.reserve(aquaa.size());
    for(int i = 0; i + 1 < (int)aquaa.size(); i++){
        if ((aquaa[i] > 0) != (aquaa[i+1] > 0))
            aqua.push_back(aquaa[i]);
    }
    // always add the final “record”
    aqua.push_back(aquaa.back());

    // 4) Precompute the dm[] = |aqua[i]| + |aqua[i+1]| array and sort it
    vector<ll> dm;
    dm.reserve(aqua.size()-1);
    for(int i = 0; i + 1 < (int)aqua.size(); i++){
        dm.push_back(llabs(aqua[i]) + llabs(aqua[i+1]));
    }
    sort(dm.begin(), dm.end());

    // 5) Sweep through the original a[1..n], splitting each gap a[i+1]-a[i]
    //    optimally between the two sides
    for(int i = 1; i < n; i++){
        ll gap = a[i+1] - a[i];
        // find the largest dm[p] <= gap
        int p = int(upper_bound(dm.begin(), dm.end(), gap) - dm.begin()) - 1;

        if(p == -1){
            // gap smaller than any dm[0]
            if(aqua[0] > 0){
                ans[i]   += min(aqua[0], gap);
                gap      -= min(aqua[0], gap);
                if(gap > 0) ans[i+1] += gap;
            } else {
                ans[i+1] += min(llabs(aqua[0]), gap);
                gap      -= min(llabs(aqua[0]), gap);
                if(gap > 0) ans[i]   += gap;
            }
        }
        else if(p == (int)dm.size()-1){
            // use the very last “flip”
            if(aqua[p] > 0){
                ans[i]   += aqua[p];
                ans[i+1] += llabs(aqua[p+1]);
            } else {
                ans[i]   += aqua[p+1];
                ans[i+1] += llabs(aqua[p]);
            }
        }
        else {
            // take dm[p] fully, then split the rest
            if(aqua[p] > 0){
                ans[i]   +=   aqua[p] + (gap - dm[p]);
                ans[i+1] += llabs(aqua[p+1]);
            } else {
                ans[i]   +=   aqua[p+1];
                ans[i+1] += llabs(aqua[p]) + (gap - dm[p]);
            }
        }
    }

    // 6) add the final dangling bits
    ans[1] += bestNeg;
    ans[n] += bestPos;

    // 7) print
    for(int i = 1; i <= n; i++){
        cout << ans[i] << "\n";
    }

    return 0;
}

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