Submission #556010

#	Time	Username	Problem	Language	Result	Execution time	Memory
556010		HeatDroppa	Distributing Candies (IOI21_candies)	C++17	100 / 100	1950 ms	50824 KiB

candies

    #include <bits/stdc++.h>
    #include "candies.h"
    #define pb push_back
    #define f first
    #define s second
    #define pi acos(-1)
     
    using namespace std;
     
    typedef long long ll;
    typedef long double ld;
     
    const ll oo = 1e18;
    const ld eps = (ld)1 / oo;
    const ll N = 2e5 + 100;
    const ll M = 1e6;
     
    struct tree
    {
        tree *L = NULL;
        tree *R = NULL;
        int l;
        int r;
        int mdl;
        ll lb = 0;
        ll mn = 0;
        ll mx = 0;
     
        tree (int _l, int _r) : l(_l), r(_r)
        {
            mdl = (l + r) >> 1;
            if (l == r) return;
            L = new tree(l, mdl);
            R = new tree(mdl + 1, r);
        }
     
        void push()
        {
            if (lb != 0)
            {
                mx += lb;
                mn += lb;
                if (l != r)
                {
                    L -> lb += lb;
                    R -> lb += lb;
                }
                lb = 0;
            }
        }
     
        void upd(int _l, int _r, int _vl)
        {
            push();
            if (_l > _r) return ;
            if (_l == l && _r == r)
            {
                lb += _vl;
                push();
                return;
            }
            L -> upd(_l, min(mdl, _r), _vl);
            R -> upd(max(mdl + 1, _l), _r, _vl);
            mn = min(L -> mn, R -> mn);
            mx = max(L -> mx, R -> mx);
        }
     
        ll calc_mx(int _l, int _r)
        {
            push();
            if (_l > _r) return -oo;
            if (_l == l && _r == r) return mx;
            return max(L -> calc_mx(_l, min(mdl, _r)), R -> calc_mx(max(mdl + 1, _l), _r));
        }
     
        ll calc_mn(int _l, int _r)
        {
            push();
            if (_l > _r) return oo;
            if (_l == l && _r == r) return mn;
            return min(L -> calc_mn(_l, min(mdl, _r)), R -> calc_mn(max(mdl + 1, _l), _r));
        }
     
    };
     
    std::vector<int> distribute_candies (std::vector<int> c, std::vector<int> l,
                                         std::vector<int> r, std::vector<int> v) {
        int n = c.size();
        int q = l.size();
        vector <pair<int, int> > event[n + 1];
        for (int i = 0; i < q; i++)
        {
            event[l[i]].pb({i + 1, v[i]});
            event[r[i] + 1].pb({i + 1, -v[i]});
        }
        tree *root = new tree(0, q);
        vector <int> ans(n);
        for (int i = 0; i < n; i++)
        {
            for (auto j : event[i]) root -> upd(j.f, q, j.s);
            int l = 0, r = q;
            while (l < r)
            {
                int mdl = (l + r + 1) >> 1;
                if (root -> calc_mx(mdl, q) - root -> calc_mn(mdl, q) < c[i]) r = mdl - 1;
                else l = mdl;
            }
            ll mx = root -> calc_mx(l, q);
            ll mn = root -> calc_mn(l, q);
            if (mx - mn <= c[i])
            {
                ans[i] = root -> calc_mx(q, q) - mn;
                continue;
            }
            else
            {
                ll mx1 = root -> calc_mx(l + 1, q);
                ll mn1 = root -> calc_mn(l + 1, q);
                if (mn < mn1) mn1 = mx1 - c[i];
                ans[i] = root -> calc_mx(q, q) - mn1;
            }
        }
        return ans;
    }
     
    //int main()
    //{
    //    int n;
    //    cin >> n;
    //    vector <int> a(n);
    //    for (int i = 0; i < n; i++) cin >> a[i];
    //    int q;
    //    cin >> q;
    //    vector <int> l(q), r(q), v(q);
    //    for (int i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];
    //    vector <int> ans = distribute_candies(a, l, r, v);
    //    for (auto i : ans) cout << i << " ";
    //}

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