제출 #441802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441802		benedict0724	Snowball (JOI21_ho_t2)	C++17	100 / 100	109 ms	15540 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll X[200002];
ll P[200002], N[200002];
vector<pair<ll, int>> v;

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> X[i];
    for(int i=1;i<n;i++) v.push_back({X[i+1] - X[i], i});

    ll Neg = 0, Pos = 0, W = 0;
    sort(v.begin(), v.end());
    for(int i=1;i<=n;i++) P[i] = -1;
    for(int i=1;i<=n;i++) N[i] = 1;
    for(int i=1,j=0;i<=q;i++)
    {
        ll A; cin >> A;
        W += A;
        Pos = max(Pos, W);
        Neg = min(Neg, W);

        while(j < n-1 && v[j].first <= Pos - Neg)
        {
            int x = v[j].second;
            if(A > 0)
            {
                N[x+1] = Neg;
                P[x] = v[j].first + Neg;
            }
            else
            {
                P[x] = Pos;
                N[x+1] = Pos - v[j].first;
            }
            j++;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(P[i] == -1) P[i] = Pos;
        if(N[i] == 1) N[i] = Neg;
    }

    for(int i=1;i<=n;i++)
    {
        cout << P[i] - N[i] << "\n";
    }
}

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