제출 #1357286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357286		12345678	Snowball (JOI21_ho_t2)	C++17	100 / 100	60 ms	9872 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=2e5+5, inf=1e18;

ll n, q, x[nx], w, cur, high, low, res[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>x[i];
    x[0]=-inf, x[n+1]=inf;
    vector<tuple<ll, ll, bool>> rec;
    while (q--)
    {
        cin>>w;
        cur+=w;
        if (cur>high) high=cur, rec.push_back({high-low, high, 0});
        if (cur<low) low=cur, rec.push_back({high-low, high, 1});
    }    
    for (int i=1; i<=n+1; i++)
    {
        ll gap=x[i]-x[i-1];
        if (high-low<=gap)
        {
            res[i-1]+=high;
            res[i]+=abs(low);
            continue;
        }
        auto [sm, h, t]=*lower_bound(rec.begin(), rec.end(), make_tuple(gap, 0, 0));
        ll curhigh=h, curlow=sm-h;
        if (t==0) curhigh=gap-curlow;
        else curlow=gap-curhigh;
        res[i-1]+=curhigh;
        res[i]+=abs(curlow);
    }
    for (int i=1; i<=n; i++) cout<<res[i]<<'\n';
}

• 서브태스크 1: 33 / 33
• 서브태스크 2: 67 / 67