Submission #443949

#	Time	Username	Problem	Language	Result	Execution time	Memory
443949		blue	Candies (JOI18_candies)	C++17	100 / 100	750 ms	17932 KiB

candies

#include <iostream>
#include <vector>
#include <set>
using namespace std;

/*
A block of candies is a set of chosen candies of the form i, i+2, ..., j
Initially, there are zero blocks.
We can add candies as follows:
    A. Take a block i, i+2, ... j and expand it to i-1, i+1, ... j+1
    B. Add a new block {i} and check if it mixes with any blocks to the left or the right.
*/
const int maxN = 200000;

int N;
long long A[2+maxN];
long long* Asum = new long long[2+maxN];

long long INF = 1'000'000'000'000'000'000LL;

struct block
{
    int i;
    int j;

    long long score()
    {
        return Asum[j] - Asum[i - 2];
    }

    long long expand_score()
    {
        if(j == N || i == 1) return -INF;
        else return Asum[j+1] - Asum[i-1 - 2];
    }

    long long gain()
    {
        return expand_score() - score();
    }
};

bool operator < (block X, block Y)
{
    if(X.gain() == Y.gain())
    {
        return X.i < Y.i;
    }
    return X.gain() > Y.gain();
}



struct new_block
{
    int i;
};

bool operator < (new_block X, new_block Y)
{
    if(A[X.i] == A[Y.i]) return X.i < Y.i;
    return A[X.i] > A[Y.i];
}



set<block> B;
set<new_block> NB;

vector<int> start_block(1+maxN, 0); //end_block of block start_blocking at i
vector<int> end_block(1+maxN, 0); //start_block of block end_blocking at i


void combine_blocks(int i)
{
    if(i < 1 || N < i) return;
    if(start_block[i] == 0 || end_block[i+2] == 0) return;

    int a = start_block[i];
    int b = end_block[i+2];

    block X = block{a, i};
    block Y = block{i+2, b};

    B.erase(X);
    B.erase(Y);

    start_block[i] = end_block[i] = start_block[i+2] = end_block[i+2] = 0;
    end_block[a] = b;
    start_block[b] = a;

    B.insert(block{a, b});
}

int main()
{
    A[0] = A[N+1] = 0;

    cin >> N;
    for(int i = 1; i <= N; i++) cin >> A[i];

    Asum = &Asum[1];
    Asum[-1] = Asum[0] = 0;
    for(int i = 1; i <= N; i++) Asum[i] = Asum[i-2] + A[i];

    for(int i = 1; i <= N; i++)
    {
        NB.insert(new_block{i});
    }

    long long ans = 0;

    for(int j = 1; j <= N/2 + N%2; j++)
    {
        // cerr << "\n\n\n\n\nj = " << j << '\n';
        // cerr << "B.size() == " << B.size() << ", NB.size() == " << NB.size() << '\n';
        // block b0 = *B.begin();
        if(B.size() == 0 || (NB.size() > 0 && A[NB.begin()->i] > block{B.begin()->i, B.begin()->j}.gain()))
        {
            // cerr << "case 1\n";
            /*
            1. Build the new block.
            2. Get rid of all (new blocks) in [i-1, i+1].
            3. See if this can be combined with a block to the left
            4. See if this can be combined with a block to the right.
            */

            int I = NB.begin()->i;
            NB.erase(NB.begin());

            // cerr << "hello\n";

            B.insert(block{I, I});
            start_block[I] = end_block[I] = I;

            // cerr << "check\n";

            if(I-1 >= 1)
                NB.erase(new_block{I-1});

            if(I+1 <= N)
                NB.erase(new_block{I+1});

            ans += A[I];

            if(I-2 >= 1)
                combine_blocks(I-2);

            if(I+2 <= N)
                combine_blocks(I);

            // cerr << "done\n";
        }
        else
        {
            int I = B.begin()->i;
            int J = B.begin()->j;
            B.erase(B.begin());

            ans += block{I, J}.gain();
            end_block[I] = start_block[J] = 0;

            B.insert(block{I-1, J+1});
            end_block[I-1] = J+1;
            start_block[J+1] = I-1;


            if(I-2 >= 1)
                NB.erase(new_block{I-2});
            if(J+2 <= N)
                NB.erase(new_block{J+2});

            combine_blocks(I-1 - 2);
            combine_blocks(J+1);
        }

        cout << ans << '\n';
    }
}

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