제출 #1175156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175156		chikien2009	Snowball (JOI21_ho_t2)	C++20	100 / 100	75 ms	8880 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, q, a, b;
long long w, change;
long long maxchange, minchange, dist;
long long x[200000], weight[200000];
priority_queue<pair<long long, pair<int, int>>> pq;
bool lock_left[200000], lock_right[200000];

int main()
{
    setup();

    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> x[i];
        if (0 < i)
        {
            pq.push({-(x[i] - x[i - 1]), {i - 1, i}});
        }
    }
    for (int i = 0; i < q; ++i)
    {
        cin >> w;
        change += w;
        minchange = min(minchange, change);
        maxchange = max(maxchange, change);
        while (!pq.empty() && maxchange - minchange >= -pq.top().first)
        {
            dist = -pq.top().first;
            a = pq.top().second.first;
            b = pq.top().second.second;
            pq.pop();
            if (w > 0)
            {
                weight[a] += dist + minchange;
                weight[b] -= minchange;
                lock_right[a] = lock_left[b] = true;
            }
            else
            {
                weight[a] += maxchange;
                weight[b] += dist - maxchange;
                lock_right[a] = lock_left[b] = true;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        cout << weight[i] + (!lock_right[i]) * maxchange - (!lock_left[i]) * minchange << "\n";
    }
    return 0;
}

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