Submission #734129

#	Time	Username	Problem	Language	Result	Execution time	Memory
734129		finn__	Distributing Candies (IOI21_candies)	C++17	0 / 100	442 ms	28488 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 200000, L = 1 << 18;

int64_t t[2 * L][3];
tuple<size_t, int64_t, size_t> events[2 * N];

void propagate(size_t k)
{
    t[2 * k][0] += t[k][2];
    t[2 * k][1] += t[k][2];
    t[2 * k][2] += t[k][2];
    t[2 * k + 1][0] += t[k][2];
    t[2 * k + 1][1] += t[k][2];
    t[2 * k + 1][2] += t[k][2];
    t[k][2] = 0;
}

void update(size_t i, size_t j, int64_t x, size_t k = 1, size_t a = 0, size_t b = L - 1)
{
    if (b < i || a > j)
        return;
    if (i <= a && b <= j)
    {
        t[k][0] += x;
        t[k][1] += x;
        t[k][2] += x;
    }
    else
    {
        propagate(k);
        update(i, j, x, 2 * k, a, (a + b) / 2);
        update(i, j, x, 2 * k + 1, (a + b) / 2 + 1, b);
        t[k][0] = max(t[2 * k][0], t[2 * k + 1][0]);
        t[k][1] = min(t[2 * k][1], t[2 * k + 1][1]);
    }
}

int64_t range_min(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
{
    if (b < i || a > j)
        return INT64_MAX;
    if (i <= a && b <= j)
        return t[k][1];
    propagate(k);
    return min(range_min(i, j, 2 * k, a, (a + b) / 2), range_min(i, j, 2 * k + 1, (a + b) / 2 + 1, b));
}

size_t last_greater(int64_t x)
{
    if (t[1][0] < x)
        return SIZE_MAX;
    size_t k = 1;
    while (k < L)
        k = t[2 * k + 1][0] > x ? 2 * k + 1 : 2 * k;
    return k - L;
}

int64_t get_value(size_t i)
{
    size_t k = 1, a = 0, b = L - 1;
    while (k < L)
    {
        propagate(k);
        if (i <= (a + b) / 2)
            k = 2 * k, b = (a + b) / 2;
        else
            k = 2 * k + 1, a = (a + b) / 2 + 1;
    }
    return t[k][0];
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    size_t const n = c.size(), q = l.size();
    for (size_t i = 0; i < q; ++i)
        events[2 * i] = {l[i], v[i], i}, events[2 * i + 1] = {r[i] + 1, -v[i], i};
    sort(events, events + 2 * q);
    auto it = events;
    vector<int> ans(n);
    for (size_t i = 0; i < n; ++i)
    {
        while (it != events + 2 * q && get<0>(*it) <= i)
        {
            update(get<2>(*it), L - 1, get<1>(*it));
            ++it;
        }
        int64_t y = max<int64_t>(0, -range_min(0, L - 1));
        size_t lgr = last_greater(c[i] - y);
        if (lgr == SIZE_MAX)
            ans[i] = get_value(L - 1) + y;
        else
            ans[i] = get_value(L - 1) + y - min(get_value(lgr) - c[i], range_min(lgr, L - 1));
    }
    return ans;
}

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