Submission #915065

#	Time	Username	Problem	Language	Result	Execution time	Memory
915065		boris_mihov	Candies (JOI18_candies)	C++17	100 / 100	249 ms	18896 KiB

candies

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n;
int a[MAXN];
llong answer[MAXN];

struct Range
{
    int l, r;
    llong sumActive;
    llong sumIn;    

    friend bool operator < (const Range &a, const Range &b)
    {
        return a.l < b.l || (a.l == b.l && a.r < b.r);
    }
};

struct Flip
{
    llong add;
    int idxL;
    int idxR;

    friend bool operator < (const Flip &a, const Flip &b)
    {
        return a.add < b.add || (a.add == b.add && a.idxL < b.idxL);
    }
};

std::set <Range> ranges;
std::set <Flip> addFlip;
std::set <std::pair <llong,int>> addAlone;
bool inAddAlone[MAXN];

void addFlips(Range range)
{
    // std::cout << "add flips: " << range.l << ' ' << 
    if (range.l > 1 && range.r < n)
    {
        addFlip.insert({a[range.l - 1] + a[range.r + 1] + range.sumIn - range.sumActive, range.l, range.r});
    }
}

void eraseFlips(Range range)
{
    if (range.l > 1 && range.r < n)
    {
        addFlip.erase(addFlip.find({a[range.l - 1] + a[range.r + 1] + range.sumIn - range.sumActive, range.l, range.r}));
    }
}

void addRange(int l, int r, llong sumActive, llong sumIn)
{
    if (l > 1)
    {
        if (inAddAlone[l - 1])
        {
            inAddAlone[l - 1] = false;
            addAlone.erase(addAlone.find({a[l - 1], l - 1}));
        } else
        {
            auto it = ranges.lower_bound({l, l, 0, 0});
            assert(it != ranges.begin());
            it = std::prev(it);

            assert(it->r == l - 2);
            eraseFlips(*it);
            sumActive += it->sumActive;
            sumIn += it->sumIn + a[l - 1];
            l = it->l;

            ranges.erase(it);
        }
    }

    if (r < n)
    {
        if (inAddAlone[r + 1])
        {
            inAddAlone[r + 1] = false;
            addAlone.erase(addAlone.find({a[r + 1], r + 1}));
        } else
        {
            auto it = ranges.upper_bound({r, r, 0, 0});
            assert(it != ranges.end());

            assert(it->l == r + 2);
            eraseFlips(*it);
            sumActive += it->sumActive;
            sumIn += it->sumIn + a[r + 1];
            r = it->r;

            ranges.erase(it);
        }
    }

    Range range = {l, r, sumActive, sumIn};
    addFlips(range);
    ranges.insert(range);
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        addAlone.insert({a[i], i});
        inAddAlone[i] = true;
    }

    int count = 0;
    llong res = 0;
    while (addFlip.size() || addAlone.size())
    {
        if (addFlip.empty() || (addAlone.size() && addAlone.rbegin()->first > addFlip.rbegin()->add))
        {
            auto [add, idx] = *addAlone.rbegin();
            addAlone.erase(addAlone.find(*addAlone.rbegin()));
            inAddAlone[idx] = false;
            res += add;

            addRange(idx, idx, a[idx], 0);
            count++;
        } else
        {
            auto [add, idxL, idxR] = *addFlip.rbegin();
            res += add;

            auto it = ranges.lower_bound({idxL, idxL - 1, 0, 0});
            assert(it != ranges.end());

            auto [l, r, sumActive, sumIn] = *it;
            assert(l == idxL && r == idxR);
            eraseFlips(*it);
            ranges.erase(it);

            addRange(idxL - 1, idxR + 1, sumIn + a[idxL - 1] + a[idxR + 1], sumActive);
            count++;
        }

        answer[count] = std::max(answer[count], res);
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void print()
{
    for (int i = 1 ; i <= (n + 1) / 2 ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92