Submission #446437

#	Time	Username	Problem	Language	Result	Execution time	Memory
446437		luciocf	Distributing Candies (IOI21_candies)	C++17	0 / 100	5098 ms	7648 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

struct Range
{
    int l, r, v;

    bool operator < (const Range &o) const
    {
        if (l == o.l)
        {
            if (r == o.r) return v < o.v;
            return r < o.r;
        }

        return l < o.l;
    }
};

multiset<Range> range;

int C;

int value(int v, int add)
{
    if (add + v > C) return C;
    if (add + v < 0) return 0;
    return add+v;
}

vector<int> distribute_candies(vector<int> c, vector<int> L, vector<int> R, vector<int> V)
{
    C = c[0];
    int n = c.size(), q = L.size();

    range.insert({1, n, 0});

    for (int i = 0; i < q; i++)
    {
        int l = L[i]+1, r = R[i]+1, v = V[i];

        auto it = range.upper_bound({l, n+1, n+1});
        it--;

        if (r <= it->r)
        {
            if (it->l != l) range.insert({it->l, l-1, it->v});

            range.insert({l, r, value(it->v, v)});

            if (r != it->r) range.insert({r+1, it->r, it->v});

            range.erase(it);

            continue;
        }

        if (it->l != l) range.insert({it->l, l-1, it->v});
        range.insert({l, it->r, value(it->v, v)});
        range.erase(it);

        for (auto it = range.upper_bound({l, n+1, n+1}); it != range.end() && it->r < r; )
        {
            Range k = {it->l, it->r, value(it->v, v)};
            it = range.erase(it);
            range.insert(k);
        }

        it = range.upper_bound({r, n+1, n+1});
        it--;

        range.insert({it->l, r, value(it->v, v)});
        if (r != it->r) range.insert({r+1, it->r, it->v});
        range.erase(it);
    }

    vector<int> ans;

    for (int i = 1; i <= n; i++)
    {
        auto it = range.upper_bound({i, n+1, n+1});
        it--;

        ans.push_back(it->v);
    }

    return ans;
}

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