oj.uz

Submission #556010

# Submission time Handle Problem Language Result Execution time Memory
556010 2022-05-02T07:17:42 Z HeatDroppa Distributing Candies (IOI21_candies) C++17
100 / 100
 1950 ms 50824 KB 
    #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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 8 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1827 ms 48984 KB Output is correct
2 Correct 1883 ms 48232 KB Output is correct
3 Correct 1950 ms 48028 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 384 ms 37208 KB Output is correct
3 Correct 349 ms 11100 KB Output is correct
4 Correct 1517 ms 50048 KB Output is correct
5 Correct 1600 ms 50452 KB Output is correct
6 Correct 1528 ms 50824 KB Output is correct
7 Correct 1622 ms 50164 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 127 ms 36000 KB Output is correct
4 Correct 328 ms 8996 KB Output is correct
5 Correct 1025 ms 43756 KB Output is correct
6 Correct 1024 ms 44536 KB Output is correct
7 Correct 887 ms 45020 KB Output is correct
8 Correct 979 ms 43660 KB Output is correct
9 Correct 949 ms 45200 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 1827 ms 48984 KB Output is correct
7 Correct 1883 ms 48232 KB Output is correct
8 Correct 1950 ms 48028 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 384 ms 37208 KB Output is correct
11 Correct 349 ms 11100 KB Output is correct
12 Correct 1517 ms 50048 KB Output is correct
13 Correct 1600 ms 50452 KB Output is correct
14 Correct 1528 ms 50824 KB Output is correct
15 Correct 1622 ms 50164 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 127 ms 36000 KB Output is correct
19 Correct 328 ms 8996 KB Output is correct
20 Correct 1025 ms 43756 KB Output is correct
21 Correct 1024 ms 44536 KB Output is correct
22 Correct 887 ms 45020 KB Output is correct
23 Correct 979 ms 43660 KB Output is correct
24 Correct 949 ms 45200 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 326 ms 8976 KB Output is correct
27 Correct 326 ms 36824 KB Output is correct
28 Correct 1691 ms 48692 KB Output is correct
29 Correct 1811 ms 49120 KB Output is correct
30 Correct 1809 ms 49268 KB Output is correct
31 Correct 1731 ms 49464 KB Output is correct
32 Correct 1661 ms 49648 KB Output is correct