Submission #1204853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204853		aquasocute	Snowball (JOI21_ho_t2)	C++17	100 / 100	62 ms	12016 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+1;

ll n, q;
ll a[N], ans[N];
vector<ll> megu, aquaa, aqua;
vector<ll> dm;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // build prefix-sums megu, bỏ x==0
    while(q--){
        ll x;
        cin >> x;
        if(x == 0) continue;
        if(megu.empty()) 
            megu.push_back(x);
        else 
            megu.push_back(megu.back() + x);
    }

    // lọc ra các đỉnh cực đại dương và âm
    ll curd = 0, curam = 0;
    for(ll it: megu){
        if(it > 0 && it > curd){
            aquaa.push_back(it);
            curd = it;
        }
        else if(it < 0 && llabs(it) > curam){
            aquaa.push_back(it);
            curam = llabs(it);
        }
    }

    // từ aquaa tạo aqua gồm các sign-change points
    if(aquaa.size() > 1){
        for(int i = 0; i + 1 < (int)aquaa.size(); i++){
            if((aquaa[i] > 0 && aquaa[i+1] < 0) ||
               (aquaa[i] < 0 && aquaa[i+1] > 0))
                aqua.push_back(aquaa[i]);
        }
    }
    if(!aquaa.empty())
        aqua.push_back(aquaa.back());

    // tạo dm và sort
    if(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());
    }

    // xử lý từng cặp a[i], a[i+1]
    for(int i = 1; i <= n-1; i++){
        if(aqua.empty()) continue;

        ll x = a[i+1] - a[i];
        int p = int(upper_bound(dm.begin(), dm.end(), x) - dm.begin()) - 1;

        if(p == int(dm.size()) - 1 && p != -1){
            // x >= hết dm
            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 if(p == -1){
            // x < dm[0]
            if(aqua[0] > 0){
                ans[i] += min(aqua[0], x);
                x -= aqua[0];
                if(x > 0) ans[i+1] += x;
            } else {
                ans[i+1] += min(llabs(aqua[0]), x);
                x -= llabs(aqua[0]);
                if(x > 0) ans[i] += x;
            }
        }
        else {
            // nằm giữa dm[p] và dm[p+1]
            if(aqua[p] > 0){
                ans[i]   += aqua[p] + (x - dm[p]);
                ans[i+1] += llabs(aqua[p+1]);
            } else {
                ans[i]   += aqua[p+1];
                ans[i+1] += llabs(aqua[p]) + (x - dm[p]);
            }
        }
    }

    // bù vào 2 đầu
    ans[1] += curam;
    ans[n] += curd;

    // output
    for(int i = 1; i <= n; i++)
        cout << ans[i] << "\n";

    return 0;
}

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