oj.uz

Submission #734129

# Submission time Handle Problem Language Result Execution time Memory
734129 2023-05-01T21:02:54 Z finn__ Distributing Candies (IOI21_candies) C++17
0 / 100
 442 ms 28488 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 28488 KB Output is correct
2 Incorrect 350 ms 28484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -