Submission #912427

#	Time	Username	Problem	Language	Result	Execution time	Memory
912427		andrei_iorgulescu	Snowball (JOI21_ho_t2)	C++14	100 / 100	77 ms	15524 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int n,q,a[200005];
int minwind = 0,maxwind = 0,wind = 0;
int lexp[200005],rexp[200005];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        lexp[i] = rexp[i] = inf;
    vector<pair<int,int>>difs;
    for (int i = 1; i < n; i++)
        difs.push_back({a[i + 1] - a[i],i});
    sort(difs.begin(),difs.end());
    reverse(difs.begin(),difs.end());
    for (int i = 1; i <= q; i++)
    {
        int x;
        cin >> x;
        wind += x;
        int mx = max(maxwind,wind);
        int mn = min(minwind,wind);
        int cur = mx - mn;
        while (!difs.empty() and difs.back().first <= cur)
        {
            int pos = difs.back().second;
            difs.pop_back();
            int extr = a[pos] + maxwind,extl = a[pos + 1] + minwind;
            if (wind > 0)
            {
                lexp[pos + 1] = a[pos + 1] + minwind;
                rexp[pos] = lexp[pos + 1];
            }
            else
            {
                rexp[pos] = a[pos] + maxwind;
                lexp[pos + 1] = rexp[pos];
            }
        }
        maxwind = mx;
        minwind = mn;
    }
    for (int i = 1; i <= n; i++)
    {
        if (lexp[i] == inf)
            lexp[i] = a[i] + minwind;
        if (rexp[i] == inf)
            rexp[i] = a[i] + maxwind;
    }
    for (int i = 1; i <= n; i++)
        cout << rexp[i] - lexp[i] << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:17: warning: unused variable 'extr' [-Wunused-variable]
   40 |             int extr = a[pos] + maxwind,extl = a[pos + 1] + minwind;
      |                 ^~~~
Main.cpp:40:41: warning: unused variable 'extl' [-Wunused-variable]
   40 |             int extr = a[pos] + maxwind,extl = a[pos + 1] + minwind;
      |                                         ^~~~

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