Submission #1165011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165011		Quentolosse	Snowball (JOI21_ho_t2)	C++20	100 / 100	173 ms	10008 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> pos(n);
    for (auto &&i : pos)
    {
        cin >> i;
    }

    vector<pair<int,int>> limites(n, {0, 0});

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> ecarts;
    for (int i = 0; i < n-1; i++)
    {
        ecarts.push({pos[i+1] - pos[i], i});
    }

    int mini = 0, maxi = 0, actuel = 0;
    for (int i = 0; i < q; i++)
    {
        int req;
        cin >> req;
        actuel += req;
        mini = min(mini, actuel);
        maxi = max(maxi, actuel);
        
        while (!ecarts.empty() && ecarts.top().first <= abs(mini) + maxi)
        {
            pair<int,int> top = ecarts.top();
            if (req < 0) {
                limites[top.second].second = maxi;
                limites[top.second + 1].first = top.first - maxi;
            }
            else {
                limites[top.second + 1].first = abs(mini);
                limites[top.second].second = top.first - abs(mini);
            }
            ecarts.pop();
        }
    }

    while (!ecarts.empty())
    {
        pair<int,int> top = ecarts.top();
        limites[top.second].second = maxi;
        limites[top.second + 1].first = abs(mini);
        ecarts.pop();
    }
    

    limites[0].first = abs(mini);
    limites[n-1].second = maxi;

    for (auto &&i : limites)
    {
        cout << i.first + i.second << endl;
    }
}

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