Submission #993743

#	Time	Username	Problem	Language	Result	Execution time	Memory
993743		NValchanov	Tortoise (CEOI21_tortoise)	C++17	100 / 100	43 ms	22988 KiB

tortoise

#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 = -1LL;
    ll last2 = -1LL;

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

            if(last2 != -1)
                after[i] = last2;
            else
                breakpoint = i;

            last2 = i;
        }
    }
}

void solve()
{
    fill_pgs();

    ll ans = 0LL;

    map < ll, ll > mp;

    for(ll i = 1; i <= n; i++)
    {
        if(a[i] <= 0)
            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 - 1)
        {
            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 - 1)
            {
                auto [x, y] = *prev(mp.end());

                if(ans - 1 * x * y > i - 1)
                {
                    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);
                    mp[x] -= z;
                    break;
                }
            }
        }

        if(ans > i - 1)
        {
            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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 25 / 25
• Subtask 5: 27 / 27