oj.uz

Submission #505181

# Submission time Handle Problem Language Result Execution time Memory
505181 2022-01-10T23:23:01 Z 0e4ef622 Distributing Candies (IOI21_candies) C++17
100 / 100
 660 ms 55448 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 4 ms 740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 50752 KB Output is correct
2 Correct 644 ms 50860 KB Output is correct
3 Correct 621 ms 50936 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 427 ms 47144 KB Output is correct
3 Correct 143 ms 8348 KB Output is correct
4 Correct 660 ms 54804 KB Output is correct
5 Correct 652 ms 55072 KB Output is correct
6 Correct 630 ms 55448 KB Output is correct
7 Correct 585 ms 54788 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 196 ms 46820 KB Output is correct
4 Correct 116 ms 7304 KB Output is correct
5 Correct 354 ms 52352 KB Output is correct
6 Correct 369 ms 52892 KB Output is correct
7 Correct 372 ms 52900 KB Output is correct
8 Correct 348 ms 52228 KB Output is correct
9 Correct 394 ms 52888 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 4 ms 740 KB Output is correct
6 Correct 621 ms 50752 KB Output is correct
7 Correct 644 ms 50860 KB Output is correct
8 Correct 621 ms 50936 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 427 ms 47144 KB Output is correct
11 Correct 143 ms 8348 KB Output is correct
12 Correct 660 ms 54804 KB Output is correct
13 Correct 652 ms 55072 KB Output is correct
14 Correct 630 ms 55448 KB Output is correct
15 Correct 585 ms 54788 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 196 ms 46820 KB Output is correct
19 Correct 116 ms 7304 KB Output is correct
20 Correct 354 ms 52352 KB Output is correct
21 Correct 369 ms 52892 KB Output is correct
22 Correct 372 ms 52900 KB Output is correct
23 Correct 348 ms 52228 KB Output is correct
24 Correct 394 ms 52888 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 102 ms 7324 KB Output is correct
27 Correct 406 ms 46736 KB Output is correct
28 Correct 611 ms 53308 KB Output is correct
29 Correct 633 ms 53704 KB Output is correct
30 Correct 633 ms 53920 KB Output is correct
31 Correct 628 ms 54192 KB Output is correct
32 Correct 613 ms 54264 KB Output is correct