Submission #1253579

#TimeUsernameProblemLanguageResultExecution timeMemory
1253579bach25089Snowball (JOI21_ho_t2)C++20
100 / 100
60 ms8264 KiB
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

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

    int n, q;
    cin >> n >> q;
    vector<long long> x(n + 2), res(n + 2);
    x[0] = -INF, x[n + 1] = INF;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
    }
    vector<pair<long long, int>> t(n + 1);
    for (int i = 0; i <= n; i++)
    {
        t[i] = make_pair(x[i + 1] - x[i], i);
    }
    sort(t.begin(), t.end());
    long long l = 0, r = 0, v = 0, p = 0;
    while (q--)
    {
        long long w;
        cin >> w;
        v += w;
        if (w >= 0)
        {
            r = max(r, v);
            while (p <= n && t[p].first < l + r)
            {
                int i = t[p].second;
                res[i] += (t[p].first - l);
                res[i + 1] += l;
                p++;
            }
        }
        else
        {
            l = max(l, -v);
            while (p <= n && t[p].first < l + r)
            {
                int i = t[p].second;
                res[i] += r;
                res[i + 1] += (t[p].first - r);
                p++;
            }
        }
    }
    while (p <= n)
    {
        int i = t[p].second;
        res[i] += r;
        res[i + 1] += l;
        p++;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << res[i] << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...