제출 #1254616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254616		tvgk	Snowball (JOI21_ho_t2)	C++20	100 / 100	53 ms	8872 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

int n, q;
ll a[mxN], ans[mxN];
ii dif[mxN];
bool vis[mxN][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dif[i - 1].fi = a[i] - a[i - 1];
        dif[i - 1].se = i - 1;
    }
    sort(dif + 1, dif + n);

    int ctr = 1;
    ll mn = 0, mx = 0;
    ll cur = 0;
    for (int i = 1; i <= q; i++)
    {
        ll tmp;
        cin >> tmp;

        cur += tmp;
        mn = min(mn, cur);
        mx = max(mx, cur);

        while (ctr < n && mx - mn >= dif[ctr].fi)
        {
            vis[dif[ctr].se][1] = 1;
            vis[dif[ctr].se + 1][0] = 1;

            if (tmp > 0)
            {
                ans[dif[ctr].se] += dif[ctr].fi + mn;
                ans[dif[ctr].se + 1] -= mn;
            }
            else
            {
                ans[dif[ctr].se] += mx;
                ans[dif[ctr].se + 1] += dif[ctr].fi - mx;
            }

            ctr++;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        ans[i] -= mn * (!vis[i][0]);
        ans[i] += mx * (!vis[i][1]);
        cout << ans[i] << '\n';
    }
}

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