제출 #832986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832986		Johann	사탕 분배 (IOI21_candies)	C++17	100 / 100	319 ms	31940 KiB

candies

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

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int INF_int = 1 << 30;

int N, Q;
vi C, L, R, V;
vector<int> ans;

struct segtree
{
    int size;
    vi sum;
    vi maxi;
    vi mini;
    const int offset = 2;
    void compute(int x)
    {
        assert(x < size);
        sum[x] = sum[2 * x] + sum[2 * x + 1];
        mini[x] = min(mini[2 * x] + sum[2 * x + 1], mini[2 * x + 1]);
        maxi[x] = max(maxi[2 * x] + sum[2 * x + 1], maxi[2 * x + 1]);
    }
    void init(int _size)
    {
        size = 1;
        while (size < _size + offset + 1)
            size *= 2;
        sum.assign(2 * size, 0);
        maxi.assign(2 * size, 0);
        mini.assign(2 * size, 0);
        sum[size] = mini[size] = maxi[size] = -INF_int;
        sum[size + 1] = mini[size + 1] = maxi[size + 1] = INF_int;
        for (int i = size - 1; i > 0; --i)
            compute(i);
    }
    void add(int i, ll v)
    {
        add(i + offset, v, 1, 0, size);
    }
    void add(int i, ll v, int x, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            sum[x] += -v;
            mini[x] = sum[x];
            maxi[x] = sum[x];
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m)
            add(i, v, 2 * x, lx, m);
        else
            add(i, v, 2 * x + 1, m, rx);
        compute(x);
    }
    ll answer(ll capa)
    {
        // way up
        ll ma = 0, mi = 0, su = 0;
        int x = 2 * size - 1;
        while (max(0LL, maxi[x]) - min(0LL, mini[x]) < capa)
        {
            ma = max(0LL, maxi[x]);
            mi = min(0LL, mini[x]);
            su = sum[x];
            x /= 2;
        }

        // waydown
        x = 2 * x;
        while (x < size)
        {
            if (max(maxi[2 * x + 1] + su, ma) - min(mini[2 * x + 1] + su, mi) < capa)
            {
                ma = max(maxi[2 * x + 1] + su, ma);
                mi = min(mini[2 * x + 1] + su, mi);
                su = su + sum[2 * x + 1];
                x = 2 * x;
            }
            else
                x = 2 * x + 1;
        }

        mi = min(mi, mini[x] + su);
        ma = max(ma, maxi[x] + su);
        su += sum[x];
        // calculation
        if (sum[x] > 0)
            return min(0 - mi, capa);
        else if (sum[x] < 0)
            return max(0LL, 0 - (ma - capa));
        else
            assert(false);
    }
};
segtree seg;

std::vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v)
{
    N = sz(_c), Q = sz(_l);

    vpii Qu(Q); // {left, idx}
    for (int i = 0; i < Q; ++i)
        Qu[i] = {_l[i], i};
    sort(all(Qu));
    reverse(all(Qu));

    seg.init(Q);

    ans.resize(N);
    priority_queue<pii, vpii, greater<pii>> q;
    for (int i = 0; i < N; ++i)
    {
        while (!Qu.empty() && get<0>(Qu.back()) <= i)
        {
            int l, idx;
            tie(l, idx) = Qu.back();
            Qu.pop_back();
            seg.add(idx, _v[idx]);
            q.push({_r[idx], idx});
        }

        ans[i] = seg.answer(_c[i]);

        while (!q.empty() && q.top().first <= i)
        {
            int r, idx;
            tie(r, idx) = q.top();
            q.pop();
            seg.add(idx, -_v[idx]);
        }
    }

    return ans;
}

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