Submission #505181

#	Time	Username	Problem	Language	Result	Execution time	Memory
505181		0e4ef622	Distributing Candies (IOI21_candies)	C++17	100 / 100	660 ms	55448 KiB

candies

#include <bits/stdc++.h>
#define F first
#define S second
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define bck(i, a, b) if ((i) >= (a) && (i) < (b))
#define trav(x, a) for (auto &x : (a))
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define dbg(X) std::cerr << "[DBG]("<<__FUNCTION__<<":"<<__LINE__<<") " << #X << ": " << X << std::endl;
using namespace std;
typedef long long ll;
typedef string str;
template<typename T> using vec = vector<T>;
template<typename T> using pq = priority_queue<T, vector<T>, std::greater<T>>;
template<typename T> using mxpq = priority_queue<T>;
typedef pair<int,int> pii;
typedef vec<int> vi;
typedef vec<pii> vii;
typedef vec<vi> vvi;
typedef pair<ll,ll> pll;
typedef vec<ll> vl;
typedef vec<pll> vll;
typedef vec<vl> vvl;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename A, typename B>
istream& operator>>(istream& s, pair<A,B>& p) { return s>>p.first>>p.second; }
template<typename A, typename B>
ostream& operator<<(ostream& s, const pair<A,B>& p) { s << "(" << p.F << ", " << p.S << ")"; return s; }
template<typename T>
istream& operator>>(istream& s, vec<T>& p) { for (T& t : p) s >> t; return s; }
template<typename T>
ostream& operator<<(ostream& s, const vec<T>& p) { for (const T& t : p) s << t << " "; return s; }

// monoid
struct S {
    // id
    ll mn = LLONG_MAX, mx = LLONG_MIN;
    int mni, mxi;
    int i = INT_MAX;
    int len = 0;
    S() {}
    S(ll v, int j) : mn(v), mx(v), mni(j), mxi(j), i(j), len(1) {}
    S(ll mn, ll mx, int mni, int mxi, int j, int len) : mn(mn), mx(mx), mni(mni), mxi(mxi), i(j), len(len) {}
    S operator+(S o) {
        if (mn < o.mn) o.mn = mn, o.mni = mni;
        else if (mn == o.mn) ckmin(o.mni, mni);
        if (mx > o.mx) o.mx = mx, o.mxi = mxi;
        else if (mx == o.mx) ckmin(o.mxi, mxi);
        ckmin(o.i, i);
        o.len += len;
        return o;
    }
};

// update
struct U {
    ll v = 0;
    static U add(ll x) { return {x}; }
    // apply
    S operator()(S a) {
        a.mn += v;
        a.mx += v;
        return a;
    }
    // compose
    U operator()(U o) {
        return o.v += v, o;
    }
};

struct seg {
    int l, r;
    S v; U u;
    seg *lt=0, *rt=0;
    seg(const vl& a) : seg(a, 0, sz(a)) {}
    seg(const vl& a, int l, int r) : l(l), r(r) {
        if (l+1 == r) v = S(a[l], l);
        else {
            int m = (l+r)/2;
            lt = new seg(a, l, m);
            rt = new seg(a, m, r);
            v = lt->v + rt->v;
        }
    }
    void update(int s, int e, U upd) {
        if (l >= e || r <= s) return;
        if (l >= s && r <= e) u = upd(u);
        else {
            push();
            lt->update(s, e, upd);
            rt->update(s, e, upd);
            pull();
        }
    }
    S query(int s, int e) {
        if (e <= l || s >= r) return S();
        if (l >= s && r <= e) return u(v);
        else return u(lt->query(s,e) + rt->query(s,e));
    }
    S bs(int cap, S s=S()) {
        auto e = u(v) + s;
        if (e.mx - e.mn <= cap) return e;
        else if (l+1 == r) return s;
        else {
            push();
            pull();
            e = rt->u(rt->v) + s;
            if (e.mx - e.mn <= cap) return lt->bs(cap, e);
            else return rt->bs(cap, s);
        }
    }
    void pull() { v = lt->u(lt->v) + rt->u(rt->v); }
    void push() {
        lt->u = u(lt->u);
        rt->u = u(rt->u);
        u = U();
    }
};

vi distribute_candies(vi i1, vi i2, vi i3, vi i4) {
    int n = sz(i1);
    int q = sz(i2);

    vl c(all(i1));
    vec<pair<pii, ll>> u(sz(i2));
    rep(i, 0, sz(i2)) u[i] = {{i2[i], i3[i]}, i4[i]};
    trav(v, u) v.F.S++;

    vii ev;
    rep(i,0,n) ev.pb({i, INT_MAX});
    rep(i,0,q) ev.pb({u[i].F.F, i}), ev.pb({u[i].F.S, -i-1});
    sort(all(ev));

    seg s((vl(q+1)));
    vi ans(n);
    trav(e, ev) {
        auto [ai, qi] = e;
        if (qi == INT_MAX) {
            S rr = s.bs(c[ai]);
            int r = rr.i;
            S w = s.query(r, q+1);
            ll x = s.query(q, q+1).mn;

            ans[ai] = x - w.mn;
            if (r) {
                ll g = s.query(r-1, r).mn;
                if (g < w.mn) {
                    ans[ai] = x - w.mx + c[ai];
                }
            }
        } else if (qi >= 0) {
            s.update(qi+1, q+1, U::add(u[qi].S));
        } else {
            qi = -qi-1;
            s.update(qi+1, q+1, U::add(-u[qi].S));
        }
    }
    return ans;
}

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