Submission #436857

#	Time	Username	Problem	Language	Result	Execution time	Memory
436857		blue	Distributing Candies (IOI21_candies)	C++17	27 / 100	751 ms	42792 KiB

candies

#include "candies.h"
#include <vector>
using namespace std;

/*
Consider 'machines' of √Q updates.

Each machine has three numbers a, b and c such that
-> If <= a candies are inserted, a+c candies are obtained.
-> If >= b candies are inserted, b+c candies are obtained.
-> If I candies are inserted, where a <= I <= b, I+c candies are obtained.

To compute the numbers of a machine:
- Pass 0 through the machine to get l
- Pass INF through the machine to get r
- r-l = b-a


*/
int lim; //GOOD

struct machine //GOOD
{
    int a;
    int b;
    int c;

    int res(int u) //GOOD
    {
        if(u < a) return a+c;
        else if(a <= u && u <= b) return u+c;
        else return b+c;
    }
};

machine get_machine(int v)
{
    int a, b, c;
    c = v;
    if(v > 0)
    {
        a = 0;
        b = max(0, lim - v);
    }
    else
    {
        a = min(-v, lim);
        b = lim;
    }
    return machine{a, b, c};
}

machine combine(machine A, machine B)
{
    /*
        1. A.out and B.in are disjoint
            1.1     A.out is below B.in
            1.2     A.out is above B.in
        2. A.out and B.in are not disjoint
            2.1     A.out is a superset of B.in
            2.2     A.out is a subset of B.in
            2.3     A.out is below B.in
            2.4     A.out is above B.in
    */

    int a, b, c;


    if(A.b + A.c < B.a) //1.1
    {
        a = 0;
        b = 0;
        c = B.a + B.c;
    }
    else if(A.a + A.c > B.b)
    {
        a = 0;
        b = 0;
        c = B.b + B.c;
    }
    else
    {
        if(A.a + A.c <= B.a && B.b <= A.b + A.c)
        {
            a = B.a - A.c;
            b = B.b - A.c;
            c = A.c + B.c;
        }
        else if(B.a <= A.a + A.c && A.b + A.c <= B.b)
        {
            a = A.a;
            b = A.b;
            c = A.c + B.c;
        }
        else if(A.a + A.c <= B.a)
        {
            a = B.a - A.c;
            b = A.b;
            c = A.c + B.c;
        }
        else
        {
            a = A.a;
            b = B.b - A.c;
            c = A.c + B.c;
        }
    }

    return machine{a, b, c};
}

machine empty_machine()
{
    return machine{0, lim, +0};
}

struct segtree
{
    int l;
    int r;
    machine x = empty_machine();

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void update(int I, machine X)
    {
        if(I < l || r < I) return;
        else if(l == r) x = X;
        else
        {
            left->update(I, X);
            right->update(I, X);
            x = combine(left->x, right->x);
        }
    }

    int pass_input(int H)
    {
        return x.res(H);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int N = c.size();
    int Q = l.size();

    lim = c[0];

    segtree S(0, Q);

    vector<int> insertions[N], removals[N];
    for(int i = 0; i < Q; i++)
    {
        insertions[ l[i] ].push_back(i);
        removals[ r[i] ].push_back(i);
    }

    vector<int> res(N, 0);
    for(int i = 0; i < N; i++)
    {
        for(int o: insertions[i])
        {
            S.update(o, get_machine(v[o]));
        }

        res[i] = S.pass_input(0);

        for(int o: removals[i])
        {
            S.update(o, empty_machine());
        }
    }

    return res;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33