Submission #1122473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122473		osmanay	Snowball (JOI21_ho_t2)	C++17	0 / 100	0 ms	320 KiB

Main

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector <int> x(n), w(q), mx(q + 1), mn(q + 1);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    int cur = 0;
    for (int i = 0; i < q; ++i) {
        cin >> w[i];
        cur += w[i];
        mx[i + 1] = max(mx[i], cur);
        mn[i + 1] = min(mn[i], cur);
    }

    vector <int> ans(n);
    ans.front() -= mn.back();
    ans.back() += mx.back();
    for (int i = 0; i + 1 < n; ++i) {
        int d = x[i + 1] - x[i];
        if (mx.back() - mn.back() < d) {
            ans[i] += mx.back();
            ans[i + 1] -= mn.back();
        }
        else {
            int l = 0, r = q;
            while (l < r - 1) {
                int m = (l + r) / 2;
                if (mx[m] - mn[m] < d) {
                    l = m;
                }
                else {
                    r = m;
                }
            }
            ans[i] += mx[l];
            ans[i + 1] -= mn[l];
            int os = d - mx[l] + mn[l];
            if (w[l] > 0) {
                ans[i] += os;
            }
            else {
                ans[i + 1] += os;
            }
        }
    }
    for (int e : ans) {
        cout << e << '\n';
    }
}

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