oj.uz

답안 #734133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734133 2023-05-01T21:16:30 Z finn__ 사탕 분배 (IOI21_candies) C++17
8 / 100
 365 ms 26180 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 abs_min_index()
{
    size_t k = 1;
    while (k < L)
    {
        propagate(k);
        k = t[2 * k][1] < t[2 * k + 1][1] ? 2 * k : 2 * k + 1;
    }
    return k - L;
}

size_t last_greater(int64_t x)
{
    if (t[1][0] < x)
        return SIZE_MAX;
    size_t k = 1;
    while (k < L)
    {
        propagate(k);
        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 || (y > 0 && lgr < abs_min_index()))
            ans[i] = get_value(L - 1) + y;
        else
            ans[i] = get_value(L - 1) + y - min(get_value(lgr) + y - c[i], range_min(lgr + 1, L - 1) + y);
    }
    return ans;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 351 ms 26180 KB Output is correct
2 Correct 365 ms 26084 KB Output is correct
3 Correct 344 ms 26180 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -