oj.uz

Submission #993736

# Submission time Handle Problem Language Result Execution time Memory
993736 2024-06-06T10:43:48 Z NValchanov Tortoise (CEOI21_tortoise) C++17
18 / 100
 2 ms 6744 KB 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const ll MAXN = 1LL * (5e6 + 10LL);
const ll INF = 1LL * (4e18 + 10LL);

ll n;
ll a[MAXN];
ll lpg[MAXN];
ll rpg[MAXN];
ll after[MAXN];
ll sum;
ll breakpoint;

void read()
{
    cin >> n;
    for(int i = 1LL; i <= n; i++)
    {
        cin >> a[i];
        if(a[i] != -1LL)
            sum += a[i];
    }
}

void fill_pgs()
{
    breakpoint = -1LL;

    ll last = -1LL;
    for(ll i = 1LL; i <= n; i++)
    {
        if(a[i] == -1LL)
            last = i;
        else if(last != -1LL)
            lpg[i] = last;
    }

    last = -1;

    for(ll i = n; i >= 1LL; i--)
    {
        if(a[i] == -1LL)
            last = i;
        else if(a[i] != 0LL)
        {
            if(last != -1LL)
                rpg[i] = last;
        }
    }

    last = -1LL;

    for(ll i = n; i >= 1LL; i--)
    {
        if(a[i] != 0LL)
        {
            if(last != -1LL)
                after[i] = last;
            else
                breakpoint = i;

            last = i;
        }
    }
}

void solve()
{
    fill_pgs();

    ll ans = 0LL;

    map < ll, ll > mp;

    for(ll i = 1LL; i <= n; i++)
    {
        if(a[i] <= 0LL)
            continue;

        ll tim = INF;

        if(lpg[i])
            tim = min(tim, 1LL * 2LL * (i - lpg[i]));
        if(rpg[i])
            tim = min(tim, 1LL * 2LL * (rpg[i] - i));

        ll tmp = tim;

        if(after[i] && rpg[i])
        {
            tmp = (after[i] < rpg[i] ? min(tmp, 1LL * 2LL * (rpg[i] - after[i])) : 0LL);
        }

        if(i == breakpoint)
            tmp = 0LL;

        a[i]--;

        while(a[i] && ans <= i - 1LL)
        {
            mp[tim]++;
            ans += tim;
            a[i]--;
        }

        if(a[i])
        {
            if(prev(mp.end()) -> first >= tim)
            {
                mp[tim] += a[i];
                ans += (tim  * a[i]);
            }

            while(!mp.empty() && ans > i - 1LL)
            {
                auto [x, y] = *prev(mp.end());
                if(ans - 1LL * x * y > i - 1LL)
                {
                    ans -= 1LL * (x * y);
                    mp.erase(prev(mp.end()));
                }
                else
                {
                    ll diff = ans - (i - 1LL);
                    ll z = 1LL * (diff - 1LL) / x;

                    ans -= 1LL * (x * z);
                    break;
                }
            }
        }

        if(ans > i - 1LL)
        {
            if(prev(mp.end()) -> first >= tmp)
            {
                auto [x, y] = *prev(mp.end());

                ans -= x;
                mp[x]--;

                if(!mp[x])
                    mp.erase(prev(mp.end()));
                
                ans += tmp;
                mp[tmp]++;
            }
        }
        else
        {
            ans += tmp;
            mp[tmp]++;
        }
    }

    for(auto it = mp.begin(); it != mp.end(); it++)
    {
        sum -= (it -> second);
    }

    cout << sum << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6612 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6612 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6488 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6492 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6612 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6488 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6492 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Incorrect 1 ms 6492 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6612 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6488 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6492 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Incorrect 1 ms 6492 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6612 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6488 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6492 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Incorrect 1 ms 6492 KB Output isn't correct
44 Halted 0 ms 0 KB -