Submission #444176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
444176	2021-07-13T09:05:56 Z	palilo	Snowball (JOI21_ho_t2)	C++17	0 / 100	1 ms	332 KB

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());
    w.erase(remove(w.begin(), w.end(), 0), w.end());
    if (w.empty()) {
        for (int i = 0; i < n; ++i) {
            cout << "0\n";
        }
        return 0;
    }
    debug(w);
    vector<int64_t> d = {0};
    for (int i = 0, j; i != int(w.size()); i = j) {
        const bool lhs = w[i] < 0;
        int64_t farthest = w[i];
        for (j = i + 1; j != int(w.size()); ++j) {
            if (lhs) {
                if (w[j] > 0) {
                    break;
                }
                chmin(farthest, w[j]);
            } else {
                if (w[j] < 0) {
                    break;
                }
                chmax(farthest, w[j]);
            }
        }
        if (d.size() < 3 || abs(farthest) > abs(d.end()[-2])) {
            d.emplace_back(farthest);
        }
    }
    assert(d.size() >= 2);
    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() -= d.back() < 0 ? d.back() : (d.size() > 1 ? d.end()[-2] : 0);
    ans.back() += d.back() > 0 ? d.back() : (d.size() > 1 ? d.end()[-2] : 0);
    for (int i = 0; i < n - 1; ++i) {
        auto gap = a[i + 1] - a[i];
        const auto it = binary(gap);
        cout << gap << ' ' << d[it] << ' ' << d[it + 1] << '\n';
        if (d[it] > 0) {
            ans[i] += min(gap, d[it]), gap -= d[it];
        } else {
            ans[i + 1] += min(gap, -d[it]), gap += d[it];
        }
        if (d[it + 1] > 0) {
            ans[i] += min(gap, d[it + 1]);
        } else {
            ans[i + 1] += min(gap, -d[it + 1]);
        }
    }
    for (const auto& x : ans) {
        cout << x << '\n';
    }
}

Subtask #1

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-