Submission #1355532

#TimeUsernameProblemLanguageResultExecution timeMemory
1355532guardianecSnowball (JOI21_ho_t2)C++20
100 / 100
54 ms11476 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

    ll n,q;
    cin >> n >> q;
    vector<ll> x(n);
    for (int i=0; i<n; i++) {
        cin >> x[i];
    }

    vector<ll> qu(q);
    vector<ll> l(q+1),r(q+1),s(q+1);
    ll curr = 0;
    for (int i=1; i<=q; i++) {
        cin >> qu[i-1];
        curr+=qu[i-1];
        l[i] = min(l[i-1], curr);
        r[i] = max(r[i-1], curr);
        s[i] = abs(l[i])+r[i];
    }

    vector<ll> res(n);
    res[0]+=abs(l[q]);
    res[n-1]+=r[q];
    for (int i=0; i<n-1; i++) {
        ll d = x[i+1]-x[i];
        auto it = lower_bound(s.begin(), s.end(), d);
        if (it==s.end()) {
            res[i]+=r[q];
            res[i+1]+=abs(l[q]);
            continue;
        }
        ll j = it-s.begin();
        if (r[j]>r[j-1]) {
            res[i]+=d-abs(l[j-1]);
            res[i+1]+=abs(l[j-1]);
        } else {
            res[i]+=r[j-1];
            res[i+1]+=d-r[j-1];
        }
    }

    for (auto i : res) cout << i << " ";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...