Submission #581632

#	Time	Username	Problem	Language	Result	Execution time	Memory
581632		georgievskiy	Distributing Candies (IOI21_candies)	C++17	0 / 100	90 ms	16824 KiB

candies

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

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

struct ST {
    ll t[4 * N], mn[4 * N], mx[4 * N];
    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;
    }
};

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;
    vector<int> ans(n);

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

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

        int last_under = -1;
        if (st.get_min(0, 0, q, 0, q) < 0) {
            int l = 0, r = q;
            while (r - l > 1) {
                int mid = (r + l) / 2;
                if (st.get_min(0, 0, q, mid, q) < 0)
                    l = mid;
                else
                    r = mid;
            }
            last_under = l;
        }

        if (last_over > last_under) {
            ans[i] = 1ll * c[i] + st.get_val(0, 0, q, q - 1) - st.get_val(0, 0, q, last_over);
        } else {
            ans[i] = st.get_val(0, 0, q, q - 1) - st.get_val(0, 0, q, last_under);
        }
        ans[i] = min(ans[i], c[i]);
        ans[i] = max(ans[i], 0);
    }
    return ans;
}

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