Submission #916317

#TimeUsernameProblemLanguageResultExecution timeMemory
916317ace5Snowball (JOI21_ho_t2)C++17
100 / 100
74 ms16408 KiB
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    int x[n];
    vector<pair<int,int>> cc;
    vector<int> ans(n);
    for(int i = 0;i < n;++i)
    {
        cin >> x[i];
        if(i > 0)
        {
            cc.push_back({x[i]-x[i-1],i-1});
        }
    }
    sort(cc.begin(),cc.end());
    int yk = 0;
    int lg = 0,rg = 0;
    int w[q];
    int sum = 0;
    for(int i = 0;i < q;++i)
    {
        cin >> w[i];
        sum += w[i];
        if(sum < lg)
        {
            lg = sum;
            while(yk < n-1 && cc[yk].first <= rg-lg)
            {
                ans[cc[yk].second] += rg;
                ans[cc[yk].second+1] += cc[yk].first-rg;
                yk++;
            }
        }
        else if(sum > rg)
        {
            rg = sum;
            while(yk < n-1 && cc[yk].first <= rg-lg)
            {
             //   cout << cc[yk].second << ' ' << lg << ' ' << rg << "\n";
                ans[cc[yk].second+1] += abs(lg);
                ans[cc[yk].second] += cc[yk].first-abs(lg);
                yk++;
            }
        }
    }
    while(yk < n-1)
    {
        ans[cc[yk].second+1] += abs(lg);
        ans[cc[yk].second] += rg;
        yk++;
    }
    ans[0] += abs(lg);
    ans[n-1] += rg;
    for(int i = 0;i < n;++i)
    {
        cout << ans[i] << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...