Submission #621511

#	Time	Username	Problem	Language	Result	Execution time	Memory
621511		resting	Distributing Candies (IOI21_candies)	C++17	100 / 100	549 ms	69620 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define inf 0x7FFFFFFF
#define ff first
#define ss second

struct info {
    ll mn, mx, sm, mnp, mxp;
    info() : mn(inf), mx(-inf), sm(0), mnp(-1), mxp(-1){};
    info(ll p) : mn(inf), mx(-inf), sm(0), mnp(p), mxp(p){};
    info(ll v, ll p) : mn(v), mx(v), sm(v), mnp(p), mxp(p){};
};
struct node {
    ll l, r;  // mleft, right
    info d;
    node() : node(-1, -1){};
    node(ll l, ll r) : l(l), r(r){};
};

struct st {
    vector<node> t;
    const ll n;
    st(ll n) : t(n * 4), n(n) { build(0, n - 1, 0); }
    void build(ll l, ll r, ll x) {
        t[x] = node(l, r);
        if (l == r) t[x].d = info(l);
        if (l == r) return;
        ll m = l + r >> 1;
        build(l, m, x * 2 + 1);
        build(m + 1, r, x * 2 + 2);
        merge(x);
    }

    void upd(ll i, ll v, ll x = 0) {
        if (t[x].l > i || t[x].r < i) return;
        if (t[x].l == t[x].r) {
            t[x].d = info(v, i);
            return;
        }
        upd(i, v, x * 2 + 1);
        upd(i, v, x * 2 + 2);
        merge(x);
    }

    ll q(ll c) {
        info d = query(c);
        if (d.mnp < d.mxp) {
            // touches top wall??
            return c + sum(d.mxp + 1, n - 1);
        } else {
            return sum(d.mnp + 1, n - 1);
        }
    }

    ll sum(ll l, ll r, ll x = 0) {
        if (t[x].l > r || t[x].r < l) return 0;
        if (t[x].l >= l && t[x].r <= r) return t[x].d.sm;
        return sum(l, r, x * 2 + 1) + sum(l, r, x * 2 + 2);
    }

    info query(ll c, info d = info(), ll x = 0) {
        if (t[x].l == t[x].r) return merge(t[x].d, d);
        info tmp = merge(t[x * 2 + 2].d, d);
        if (tmp.mx - tmp.mn >= c) {
            return query(c, d, x * 2 + 2);
        }
        return query(c, tmp, x * 2 + 1);
    }

    void merge(ll x) {
        t[x].d = merge(t[x * 2 + 1].d, t[x * 2 + 2].d);
    }

    info merge(info a, info b) {
        info c;
        c.sm = a.sm + b.sm;
        if (a.mn < a.sm + b.mn) {
            c.mn = a.mn;
            c.mnp = a.mnp;
        } else {
            c.mn = a.sm + b.mn;
            c.mnp = b.mnp;
        }
        if (a.mx > a.sm + b.mx) {
            c.mx = a.mx;
            c.mxp = a.mxp;
        } else {
            c.mx = a.sm + b.mx;
            c.mxp = b.mxp;
        }
        return c;
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    const ll n = c.size();
    const ll q = l.size();
    std::vector<int> s(n);
    st ac(q + 2);
    ac.upd(0, inf);
    ac.upd(1, -inf);
    vector<vector<pair<int, int>>> qs(n + 1);
    for (int i = 0; i < q; i++) {
        qs[l[i]].push_back({i + 2, v[i]});
        qs[r[i] + 1].push_back({i + 2, 0});
    }
    for (int i = 0; i < n; i++) {
        for (auto &x : qs[i])
            ac.upd(x.ff, x.ss);
        s[i] = ac.q(c[i]);
    }

    return s;
}

Compilation message (stderr)

candies.cpp: In member function 'void st::build(long long int, long long int, long long int)':
candies.cpp:32:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         ll m = l + r >> 1;
      |                ~~^~~

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