제출 #637555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637555		danikoynov	Snowball (JOI21_ho_t2)	C++14	33 / 100	231 ms	18640 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll inf = 1e17;
const int maxn = 2e5 + 10;

int n, q;
ll a[maxn], flf[maxn], frf[maxn], ans[maxn];

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    a[0] = - inf;
    a[n + 1] = inf;

    vector < pair < ll, ll > > vlf, vrf;
    for (int i = 1; i <= n; i ++)
    {
        flf[i] = 1;
        frf[i] = 1;
        vlf.push_back({a[i] - a[i - 1], i});
        vrf.push_back({a[i + 1] - a[i], i});
    }

    sort(vlf.begin(), vlf.end());
    sort(vrf.begin(), vrf.end());
    ll pos = 0, dlf = 0, drf = 0, ptlf = 0, ptrf = 0;
    for (int i = 1; i <= q; i ++)
    {
        ll x;
        cin >> x;
        pos += x;
        if (pos <= drf && pos >= dlf)
            continue;

        if (pos > drf)
        {
            drf = pos;
            while(drf + abs(dlf) >= vrf[ptrf].first)
            {
                ans[vrf[ptrf].second] += (vrf[ptrf].first - abs(dlf));
                frf[vrf[ptrf].second] = 0;
                ptrf ++;
            }
            while(drf + abs(dlf) >= vlf[ptlf].first)
            {
                ans[vlf[ptlf].second] += + abs(dlf);
                flf[vlf[ptlf].second] = 0;
                ptlf ++;
            }
            /**for (int j = 1; j <= n; j ++)
            {
                if (frf[j])
                {
                    if (drf + abs(dlf) >= a[j + 1] - a[j])
                    {
                        ///cout << j << " : " << i << " ::: " << dlf << endl;
                        ans[j] = ans[j] + (a[j + 1] - a[j] - abs(dlf));
                        frf[j] = 0;
                    }
                }

                if (flf[j])
                {
                    if (drf + abs(dlf) >= a[j] - a[j - 1])
                    {
                        ans[j] = ans[j] + abs(dlf);
                        flf[j] = 0;
                    }
                }
            }*/
        }
        else
        if (pos < dlf)
        {
            dlf = pos;
                        while(drf + abs(dlf) >= vrf[ptrf].first)
            {
                ans[vrf[ptrf].second] += drf;
                frf[vrf[ptrf].second] = 0;
                ptrf ++;
            }
                        while(drf + abs(dlf) >= vlf[ptlf].first)
            {
                ans[vlf[ptlf].second] += (vlf[ptlf].first - drf);
                flf[vlf[ptlf].second] = 0;
                ptlf ++;
            }
            /**for (int j = 1; j <= n; j ++)
            {
                if (frf[j])
                {
                    if (drf + abs(dlf) >= a[j + 1] - a[j])
                    {
                        ans[j] = ans[j] + drf;
                        frf[j] = 0;
                    }
                }

                if (flf[j])
                {
                    if (drf + abs(dlf) >= a[j] - a[j - 1])
                    {
                        ans[j] = ans[j] + (a[j] - a[j - 1] - drf);
                        flf[j] = 0;
                    }
                }
            }*/
        }
    }

    for (int i = 1; i <= n; i ++)
    {
        ll sum = ans[i];
        if (flf[i] == 1)
        sum = sum + abs(dlf);
        if (frf[i] == 1)
            sum = sum + drf;
        cout << sum << endl;
    }

}

int main()
{
    solve();
    return 0;
}

/**
4 3
-2 3 5 8
2
-4
7

*/

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