Submission #444490

#	Time	Username	Problem	Language	Result	Execution time	Memory
444490		palilo	Snowball (JOI21_ho_t2)	C++17	100 / 100	138 ms	9528 KiB

Main

#include <bits/stdc++.h>
using namespace std;

template <class T>
bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); }
template <class T>
bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); }

#ifdef palilo
template <typename C, typename T = decay_t<decltype(*begin(declval<C>()))>,
    typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator<<(ostream& os, const C& container) {
    stringstream ss;
    ss << '[';
    bool first = true;
    for (const auto& x : container) {
        if (!first) ss << ", ";
        first = false;
        ss << x;
    }
    ss << ']';
    return os << ss.str();
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    stringstream ss;
    ss << '(' << p.first << ", " << p.second << ')';
    return os << ss.str();
}

template <typename T>
void debug_msg(string name, T arg) {
    cerr << name << " = " << arg << endl;
}

template <typename T1, typename... T2>
void debug_msg(string names, T1 arg, T2... args) {
    cerr << names.substr(0, names.find(',')) << " = " << arg << " | ";
    debug_msg(names.substr(names.find(',') + 2), args...);
}

#define debug(...) cerr << '(' << __LINE__ << ')' << ' ', debug_msg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#endif

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n, q;
    cin >> n >> q;
    vector<int64_t> a(n), w(q);
    for (auto& x : a) {
        cin >> x;
    }
    for (auto& x : w) {
        cin >> x;
    }
    partial_sum(w.begin(), w.end(), w.begin());
    debug(w);
    vector<int64_t> d;
    for (int i = 0, j; i != q;) {
        if (w[i] == 0) {
            ++i;
            continue;
        }
        const bool lhs = w[i] < 0;
        auto farthest = w[i];
        for (j = i + 1; j != q; ++j) {
            if (lhs) {
                if (w[j] > 0) {
                    break;
                }
                chmin(farthest, w[j]);
            } else {
                if (w[j] < 0) {
                    break;
                }
                chmax(farthest, w[j]);
            }
        }
        debug(d, farthest);
        i = j;
        if (!d.empty() && (d.back() < 0) == lhs) {
            if (lhs) {
                chmin(d.back(), farthest);
            } else {
                chmax(d.back(), farthest);
            }
            continue;
        }
        if (d.size() > 1 && (d.end()[-2] < 0) == lhs && abs(d.end()[-2]) >= abs(farthest)) {
            continue;
        }
        d.emplace_back(farthest);
    }
    if (d.empty()) {
        for (int i = 0; i < n; ++i) {
            cout << "0\n";
        }
        return 0;
    }
    if (d.size() == 1) {
        const bool lhs = d.front() < 0;
        const auto snow = abs(d.front());
        if (lhs) {
            cout << snow << '\n';
        }
        for (int i = 0; i < n - 1; ++i) {
            cout << min(snow, a[i + 1] - a[i]) << '\n';
        }
        if (!lhs) {
            cout << snow;
        }
        return 0;
    }
    auto binary = [&](int64_t val) {
        int lo = 0, hi = d.size() - 2;
        while (lo != hi) {
            const int mid = (lo + hi) >> 1;
            abs(d[mid]) + abs(d[mid + 1]) < val ? lo = mid + 1 : hi = mid;
        }
        return lo;
    };
    debug(d);
    vector<int64_t> ans(n);
    ans.front() -= min(d.end()[-2], d.end()[-1]);
    ans.back() += max(d.end()[-2], d.end()[-1]);
    for (int i = 0; i < n - 1; ++i) {
        auto gap = a[i + 1] - a[i];
        const auto it = binary(gap);
        if (d[it] < 0) {
            auto snow = min(gap, -d[it]);
            ans[i + 1] += snow, gap -= snow;
            ans[i] += min(gap, d[it + 1]);
        } else {
            auto snow = min(gap, d[it]);
            ans[i] += snow, gap -= snow;
            ans[i + 1] += min(gap, -d[it + 1]);
        }
    }
    for (const auto& x : ans) {
        cout << x << '\n';
    }
}

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