Submission #777197

#	Time	Username	Problem	Language	Result	Execution time	Memory
777197		dxz05	Distributing Candies (IOI21_candies)	C++17	0 / 100	129 ms	86460 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree{
    struct node{
        long long Min, Max; // min-max suffix
        long long lazy;
        node(): Min(0), Max(0), lazy(0) {};
        node(long long x): Min(x), Max(x), lazy(0) {};
    };

    void combine(node &par, const node &lc, const node &rc){
        par.Min = min(lc.Min, rc.Min);
        par.Max = max(lc.Max, rc.Max);
    }

    node neutral_element;

    int n;
    vector<node> tree;

    SegmentTree(int _n){
        n = _n;
        tree.assign(4 * n + 5, node());
        neutral_element.Min = (long long)1e16;
        neutral_element.Max = (long long)-1e16;
    }

    void upd(int v, long long lazy){
        tree[v].Min += lazy;
        tree[v].Max += lazy;
        tree[v].lazy += lazy;
    }

    void push(int v, int tl, int tr){
        if (tl == tr || tree[v].lazy == 0) return;
        upd(v << 1, tree[v].lazy);
        upd(v << 1 | 1, tree[v].lazy);
        tree[v].lazy = 0;
    }

    void update(int v, int tl, int tr, int l, int r, long long val){
        push(v, tl, tr);
        if (l <= tl && tr <= r){
            upd(v, val);
            return;
        }
        if (tl > r || tr < l) return;

        int tm = (tl + tr) >> 1;
        update(v << 1, tl, tm, l, r, val);
        update(v << 1 | 1, tm + 1, tr, l, r, val);
        combine(tree[v], tree[v << 1], tree[v << 1 | 1]);
    }

    void update(int l, int r, long long val){
        update(1, 0, n - 1, l, r, val);
    }

    node get(int v, int tl, int tr, int l, int r){
        push(v, tl, tr);
        if (l <= tl && tr <= r) return tree[v];
        if (tl > r || tr < l) return neutral_element;
        int tm = (tl + tr) >> 1;
        node res;
        combine(res, get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
        return res;
    }

    long long get_value(int pos){
        return get(1, 0, n - 1, pos, pos).Max;
    }

    long long get_diff(int l, int r){
        node res = get(1, 0, n - 1, l, r);
        return res.Max - res.Min;
    }

};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = (int)C.size(), q = (int)V.size();

    V.insert(V.begin(), (int) -2e9), L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    V.insert(V.begin(), (int) 2e9),  L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    q += 2;

    vector<vector<int>> opening(n), closing(n);
    for (int i = 0; i < q; i++){
        opening[L[i]].push_back(i);
        closing[R[i]].push_back(i);
    }

    vector<int> ans(n, 0);

    SegmentTree st(q);
    long long sum = 0;

    for (int i = 0; i < n; i++){
        for (int k : opening[i]){
            st.update(k, q - 1, V[k]);
            sum += V[k];
        }

        int j = -1;
        int l = 0, r = q - 1;
        while (l <= r){
            int m = (l + r) >> 1;
            if (st.get_diff(m, q - 1) >= C[i]){
                j = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        assert(j != -1);

        long long diff = st.get_diff(j, q - 1) - C[i];

        long long Y = st.get_value(j);
        if (V[j] > 0){ /// full
            Y -= diff;
            ans[i] = C[i] + sum - Y;
        } else { /// empty
            Y += diff;
            ans[i] = sum - Y;
        }

        assert(0 <= ans[i] && ans[i] <= C[i]);

        for (int k : closing[i]){
            st.update(k, q - 1, -V[k]);
            sum -= V[k];
        }
    }

    return ans;
}

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