oj.uz

Submission #443949

# Submission time Handle Problem Language Result Execution time Memory
443949 2021-07-12T15:06:36 Z blue Candies (JOI18_candies) C++17
100 / 100
 750 ms 17932 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1996 KB Output is correct
2 Correct 4 ms 1996 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 4 ms 1996 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 4 ms 2032 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 3 ms 1996 KB Output is correct
9 Correct 3 ms 1984 KB Output is correct
10 Correct 3 ms 1996 KB Output is correct
11 Correct 4 ms 1996 KB Output is correct
12 Correct 4 ms 2020 KB Output is correct
13 Correct 4 ms 1996 KB Output is correct
14 Correct 4 ms 2024 KB Output is correct
15 Correct 4 ms 1996 KB Output is correct
16 Correct 4 ms 2040 KB Output is correct
17 Correct 5 ms 1996 KB Output is correct
18 Correct 4 ms 1996 KB Output is correct
19 Correct 3 ms 1996 KB Output is correct
20 Correct 3 ms 1996 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1996 KB Output is correct
2 Correct 4 ms 1996 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 4 ms 1996 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 4 ms 2032 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 3 ms 1996 KB Output is correct
9 Correct 3 ms 1984 KB Output is correct
10 Correct 3 ms 1996 KB Output is correct
11 Correct 4 ms 1996 KB Output is correct
12 Correct 4 ms 2020 KB Output is correct
13 Correct 4 ms 1996 KB Output is correct
14 Correct 4 ms 2024 KB Output is correct
15 Correct 4 ms 1996 KB Output is correct
16 Correct 4 ms 2040 KB Output is correct
17 Correct 5 ms 1996 KB Output is correct
18 Correct 4 ms 1996 KB Output is correct
19 Correct 3 ms 1996 KB Output is correct
20 Correct 3 ms 1996 KB Output is correct
21 Correct 584 ms 17764 KB Output is correct
22 Correct 601 ms 17752 KB Output is correct
23 Correct 586 ms 17804 KB Output is correct
24 Correct 305 ms 17676 KB Output is correct
25 Correct 305 ms 17608 KB Output is correct
26 Correct 301 ms 17640 KB Output is correct
27 Correct 348 ms 17932 KB Output is correct
28 Correct 408 ms 17804 KB Output is correct
29 Correct 362 ms 17808 KB Output is correct
30 Correct 346 ms 17820 KB Output is correct
31 Correct 361 ms 17860 KB Output is correct
32 Correct 340 ms 17732 KB Output is correct
33 Correct 447 ms 17484 KB Output is correct
34 Correct 453 ms 17528 KB Output is correct
35 Correct 435 ms 17576 KB Output is correct
36 Correct 641 ms 17760 KB Output is correct
37 Correct 750 ms 17892 KB Output is correct
38 Correct 631 ms 17900 KB Output is correct
39 Correct 295 ms 17584 KB Output is correct
40 Correct 302 ms 17772 KB Output is correct
41 Correct 291 ms 17604 KB Output is correct
42 Correct 344 ms 17760 KB Output is correct
43 Correct 337 ms 17808 KB Output is correct
44 Correct 349 ms 17872 KB Output is correct
45 Correct 358 ms 17888 KB Output is correct
46 Correct 382 ms 17736 KB Output is correct
47 Correct 329 ms 17772 KB Output is correct
48 Correct 453 ms 17648 KB Output is correct
49 Correct 442 ms 17700 KB Output is correct
50 Correct 445 ms 17580 KB Output is correct