Submission #625340

#	Time	Username	Problem	Language	Result	Execution time	Memory
625340		yuto1115	Distributing Candies (IOI21_candies)	C++17	100 / 100	310 ms	42828 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct S {
    ll mn, mx, sum;
};
const S e = {0, 0, 0};

constexpr S op(const S &l, const S &r) {
    return S{min(l.mn, l.sum + r.mn), max(l.mx, l.sum + r.mx), l.sum + r.sum};
}

class segtree {
    int n;
    vector<S> d;
    
    void update(int p) {
        d[p] = op(d[2 * p], d[2 * p + 1]);
    }

public:
    segtree(int _n) {
        n = 1;
        while (n < _n) n <<= 1;
        d.assign(2 * n, e);
    }
    
    void set(int p, const S &x) {
        assert(0 <= p and p < n);
        p += n;
        d[p] = x;
        while (p > 1) {
            p >>= 1;
            update(p);
        }
    }
    
    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        S pl = e, pr = e;
        while (l < r) {
            if (l & 1) pl = op(pl, d[l++]);
            if (r & 1) pr = op(d[--r], pr);
            l >>= 1, r >>= 1;
        }
        return op(pl, pr);
    }
    
    S all_prod() { return d[1]; }
    
    template<class F>
    int max_right(const F &f) {
        assert(f(e));
        if (f(d[1])) return n;
        int now = 1;
        S pl = e;
        while (now < n) {
            now *= 2;
            if (f(op(pl, d[now]))) pl = op(pl, d[now++]);
        }
        return now - n;
    }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = SZ(c);
    int q = SZ(l);
    for (int &i: r) ++i;
    vvi add(n + 1), del(n + 1);
    rep(i, q) {
        add[l[i]].pb(i);
        del[r[i]].pb(i);
    }
    segtree st(q);
    vi ans(n);
    rep(i, n) {
        for (int j: del[i]) st.set(q - 1 - j, e);
        for (int j: add[i]) st.set(q - 1 - j, S{min(0, -v[j]), max(0, -v[j]), -v[j]});
        S al = st.all_prod();
        if (al.mn == 0) continue;
        int s = st.max_right([&](const S &x) { return x.mn > al.mn; });
        al = st.prod(0, s + 1);
        if (al.mx - al.mn <= c[i]) {
            ans[i] = -al.mn;
            continue;
        }
        int ub = st.max_right([&](const S &x) { return x.mx - x.mn <= c[i]; });
        assert(ub <= s);
        S s1 = st.prod(0, ub);
        S s2 = st.prod(0, ub + 1);
        assert((s1.mn == s2.mn) ^ (s1.mx == s2.mx));
        if (s1.mx == s2.mx) {
            ans[i] = c[i] - s1.mx;
        } else {
            ans[i] = -s1.mn;
        }
        assert(0 <= ans[i] and ans[i] <= c[i]);
    }
    return ans;
}

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