Submission #582062

#	Time	Username	Problem	Language	Result	Execution time	Memory
582062		georgievskiy	Distributing Candies (IOI21_candies)	C++17	0 / 100	1381 ms	42568 KiB

candies

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

const int N = 2e5;
//const int N = 1000;
const ll inf = 2e18;


struct ST {
    ll t[4 * N], mn[4 * N], mx[4 * N];
    ll q;
    ST(){
        fill(t, t + 4 * N, 0);
        fill(mn, mn + 4 * N, 0);
        fill(mx, mx + 4 * N, 0);
    }

    inline void push(int v) {
        t[2 * v + 1] += t[v], mn[2 * v + 1] += t[v], mx[2 * v + 1] += t[v];
        t[2 * v + 2] += t[v], mn[2 * v + 2] += t[v], mx[2 * v + 2] += t[v];
        t[v] = 0;
    }
    inline void upd(int v) {
        mn[v] = min(mn[2 * v + 1], mn[2 * v + 2]), mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }

    void add(int v, int tl, int tr, int l, int r, ll d) {
        if (tl >= r || tr <= l)
            return;
        if (tl >= l && tr <= r) {
            t[v] += d, mn[v] += d, mx[v] += d;
            return;
        }
        push(v);
        int m = (tl + tr) / 2;
        add(2 * v + 1, tl, m, l, r, d);
        add(2 * v + 2, m, tr, l, r, d);
        upd(v);
    }

    ll get_min(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l)
            return inf;
        if (tl >= l && tr <= r)
            return mn[v];
        push(v);
        int m = (tl + tr) / 2;
        ll ans = min(get_min(2 * v + 1, tl, m, l, r), get_min(2 * v + 2, m, tr, l, r));
        upd(v);
        return ans;
    }

    ll get_max(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l)
            return -inf;
        if (tl >= l && tr <= r)
            return mx[v];
        push(v);
        int m = (tl + tr) / 2;
        ll ans = max(get_max(2 * v + 1, tl, m, l, r), get_max(2 * v + 2, m, tr, l, r));
        upd(v);
        return ans;
    }

    ll get_val(int v, int tl, int tr, int i) {
        if (i < tl || i >= tr)
            return 0;
        if (tl + 1 == tr)
            return t[v];
        push(v);
        int m = (tl + tr) / 2;
        ll ans;
        if (i < m)
            ans = get_val(2 * v + 1, tl, m, i);
        else
            ans = get_val(2 * v + 2, m, tr, i);
        upd(v);
        return ans;
    }

    ll get_min(int left) {
        return get_min(0, 0, q, left+1, q);
    }

    ll get_max(int left) {
        return get_max(0, 0, q, left+1, q);
    }

    ll get_val(int ind) {
        return get_val(0, 0, q, ind+1);
    }

    ll get_range(int left) {
        return get_max(left) - get_min(left);
    }
    void add(int left, int right, ll d) {
        add(0, 0, q, left + 1, right + 1, d);
    }
};

vector<pair<int, int>> ev[2 * N];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int q = l.size(), n = c.size();
    for (int i = 0; i < q; i++) {
        ev[l[i]].push_back({i, v[i]});
        ev[r[i]+1].push_back({i, -v[i]});
    }

    ST st;
    st.q = q+1;
    vector<int> ans(n);

    for (int i = 0; i < n; i++) {
        for (auto p : ev[i])
            st.add(p.first, q, p.second);

        ll range = st.get_range(-1);
        if (range <= c[i]) {
            ans[i] = st.get_val(q) - st.get_min(-1);
            continue;
        }

        int l = -1, r = q;
        while (r - l > 1) {
            int mid = (r + l) / 2;
            if (st.get_range(mid) > c[i])
                l = mid;
            else
                r = mid;
        }

        ll left_val = st.get_val(l), last_val = st.get_val(q-1);
        if (left_val > last_val) {
            ans[i] = last_val - st.get_min(l);
        } else {
            ans[i] = c[i] - st.get_max(l) + last_val;
        }
    }
    return ans;
}

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