Submission #580529

#	Time	Username	Problem	Language	Result	Execution time	Memory
580529		KoD	Distributing Candies (IOI21_candies)	C++17	8 / 100	377 ms	41044 KiB

candies

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

using std::array;
using std::pair;
using std::tuple;
using std::vector;

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

struct info {
    ll sum, min, max;
};

constexpr info unit = {0, 0, 0};

info merge(const info& l, const info& r) {
    return {l.sum + r.sum, std::min(l.min, l.sum + r.min), std::max(l.max, l.sum + r.max)};
}

struct segtree {
    int size, logn;
    vector<info> data;
    explicit segtree(const int n) {
        logn = 0;
        while ((1 << logn) < n) logn += 1;
        size = 1 << logn;
        data.resize(2 * size, unit);
    }

    void set(int i, const info& o) {
        i += size;
        data[i] = o;
        while (i > 1) {
            i >>= 1;
            data[i] = merge(data[2 * i], data[2 * i + 1]);
        }
    }

    info prod(int l, int r) const {
        l += size;
        r += size;
        info sl = unit, sr = unit;
        while (l < r) {
            if (l & 1) sl = merge(sl, data[l++]);
            if (r & 1) sr = merge(data[--r], sr);
            l >>= 1;
            r >>= 1;
        }
        return merge(sl, sr);
    }

    info prod() const {
        return data[1];
    }

    template <class F>
    int min_left(const F& f) const {
        if (f(data[1])) {
            return 0;
        }
        info acc = unit;
        int k = 1;
        while (k < size) {
            const int r = 2 * k + 1;
            if (f(merge(data[r], acc))) {
                acc = merge(data[r], acc);
                k <<= 1;
            } else {
                k = r;
            }
        }
        return k - size + 1;
    }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    const int N = C.size();
    const int Q = L.size();
    vector<vector<int>> enable(N), disable(N);
    for (int i = 0; i < Q; ++i) {
        enable[L[i]].push_back(i);
        disable[R[i]].push_back(i);
    }
    segtree seg(Q);
    vector<int> res(N);
    for (int i = 0; i < N; ++i) {
        for (const int q : enable[i]) {
            seg.set(q, {V[q], std::min(0, V[q]), std::max(0, V[q])});
        }
        const int l = seg.min_left([&](const info& x) {
            return x.max - x.min < C[i];
        });
        const ll fin = seg.prod().sum;
        if (l == 0) {
            res[i] = fin;
        } else if (V[l - 1] > 0) {
            const ll high = seg.prod(0, l).sum + seg.prod(l, Q).max;
            res[i] = C[i] - (high - fin); 
        } else {
            const ll low = seg.prod(0, l).sum + seg.prod(l, Q).min;
            res[i] = fin - low;
        }
        for (const int q : disable[i]) {
            seg.set(q, unit);
        }
    }
    return res;
}

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