Submission #637556

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
637556	2022-09-02T12:17:05 Z	danikoynov	Snowball (JOI21_ho_t2)	C++14	100 / 100	256 ms	20252 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 = 1e18;
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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	3 ms	468 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	3 ms	468 KB	Output is correct
16	Correct	4 ms	468 KB	Output is correct
17	Correct	4 ms	468 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	4 ms	340 KB	Output is correct

Subtask #2

67.0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	3 ms	468 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	3 ms	468 KB	Output is correct
16	Correct	4 ms	468 KB	Output is correct
17	Correct	4 ms	468 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	4 ms	340 KB	Output is correct
20	Correct	119 ms	308 KB	Output is correct
21	Correct	78 ms	312 KB	Output is correct
22	Correct	69 ms	340 KB	Output is correct
23	Correct	65 ms	468 KB	Output is correct
24	Correct	98 ms	1932 KB	Output is correct
25	Correct	240 ms	14572 KB	Output is correct
26	Correct	235 ms	14600 KB	Output is correct
27	Correct	225 ms	14396 KB	Output is correct
28	Correct	248 ms	14320 KB	Output is correct
29	Correct	219 ms	14224 KB	Output is correct
30	Correct	194 ms	13816 KB	Output is correct
31	Correct	190 ms	13336 KB	Output is correct
32	Correct	172 ms	13324 KB	Output is correct
33	Correct	25 ms	1944 KB	Output is correct
34	Correct	224 ms	14624 KB	Output is correct
35	Correct	211 ms	14320 KB	Output is correct
36	Correct	238 ms	14612 KB	Output is correct
37	Correct	227 ms	14364 KB	Output is correct
38	Correct	221 ms	14324 KB	Output is correct
39	Correct	220 ms	14428 KB	Output is correct
40	Correct	217 ms	14424 KB	Output is correct
41	Correct	99 ms	1468 KB	Output is correct
42	Correct	179 ms	15008 KB	Output is correct
43	Correct	247 ms	19824 KB	Output is correct
44	Correct	109 ms	2852 KB	Output is correct
45	Correct	214 ms	16524 KB	Output is correct
46	Correct	253 ms	19912 KB	Output is correct
47	Correct	249 ms	20160 KB	Output is correct
48	Correct	256 ms	20252 KB	Output is correct