답안 #637555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637555	2022-09-02T12:16:31 Z	danikoynov	Snowball (JOI21_ho_t2)	C++14	33 / 100	231 ms	18640 KB

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.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	2 ms	452 KB	Output is correct
10	Correct	2 ms	456 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	0 ms	308 KB	Output is correct
19	Correct	3 ms	468 KB	Output is correct

Subtask #2

0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	2 ms	452 KB	Output is correct
10	Correct	2 ms	456 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	0 ms	308 KB	Output is correct
19	Correct	3 ms	468 KB	Output is correct
20	Correct	81 ms	2344 KB	Output is correct
21	Correct	76 ms	2228 KB	Output is correct
22	Correct	69 ms	1976 KB	Output is correct
23	Correct	71 ms	1988 KB	Output is correct
24	Correct	73 ms	3480 KB	Output is correct
25	Correct	231 ms	18252 KB	Output is correct
26	Correct	206 ms	18272 KB	Output is correct
27	Correct	208 ms	18012 KB	Output is correct
28	Correct	210 ms	18084 KB	Output is correct
29	Correct	200 ms	17520 KB	Output is correct
30	Correct	191 ms	16992 KB	Output is correct
31	Correct	181 ms	16416 KB	Output is correct
32	Correct	154 ms	16592 KB	Output is correct
33	Correct	24 ms	2388 KB	Output is correct
34	Correct	209 ms	18640 KB	Output is correct
35	Correct	194 ms	18104 KB	Output is correct
36	Correct	212 ms	18292 KB	Output is correct
37	Correct	205 ms	18032 KB	Output is correct
38	Correct	197 ms	17876 KB	Output is correct
39	Correct	224 ms	18164 KB	Output is correct
40	Correct	210 ms	18024 KB	Output is correct
41	Runtime error	48 ms	1960 KB	Execution killed with signal 11
42	Halted	0 ms	0 KB	-