oj.uz

Submission #437141

# Submission time Handle Problem Language Result Execution time Memory
437141 2021-06-25T22:44:44 Z ivan100sic Distributing Candies (IOI21_candies) C++17
100 / 100
 446 ms 36472 KB 
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;

struct node {
    ll l, h, s;

    node(ll v = 0) : l(min(0ll, v)), h(max(0ll, v)), s(v) {}

    node(ll l, ll h, ll s) : l(l), h(h), s(s) {}

    node operator+ (const node& b) const {
        return { min(l, s + b.l), max(h, s + b.h), s + b.s };
    }
};

struct state {
    ll l, r, q;

    operator bool() const {
        return l <= r;
    }

    ll operator() (ll x) const {
        if (x < q) {
            return l;
        } else {
            return min(x - q + l, r);
        }
    }

    state(node n, ll c) {
        l = n.s - n.l;
        r = c + n.s - n.h;
        q = min(c, -n.l);
    }
};

struct segtree {
    static constexpr int maxn = 262144;

    vector<node> a;

    segtree() : a(2*maxn) {}

    void update(int p, int v) {
        p += maxn;
        a[p] = node(v);
        for (int x=p>>1; x; x>>=1) {
            a[x] = a[2*x] + a[2*x+1];
        }
    }

    ll solve(ll y, ll c, int x=1, int w=maxn) {
        if (w == 1) {
            return min(c, max(0ll, y + a[x].s));
        }
        auto st = state(a[x], c);
        if (st) {
            return st(y);
        }

        auto st_r = state(a[2*x+1], c);
        
        if (st_r) {
            return st_r(solve(y, c, 2*x, w >> 1));
        } else {
            return solve(0, c, 2*x+1, w >> 1);
        }
    }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = c.size();
    int q = l.size();
    vector<vi> e(n+1), f(n+1);
    for (int i=0; i<q; i++) {
        e[l[i]].push_back(i);
        f[r[i]+1].push_back(i);
    }
    segtree st;
    vi sol(n);
    for (int i=0; i<n; i++) {
        for (int j : e[i]) {
            st.update(j, v[j]);
        }

        for (int j : f[i]) {
            st.update(j, 0);
        }
        
        sol[i] = st.solve(0, c[i]);
    }
    return sol;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12592 KB Output is correct
2 Correct 7 ms 12492 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 8 ms 12620 KB Output is correct
5 Correct 9 ms 12772 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 36240 KB Output is correct
2 Correct 404 ms 36472 KB Output is correct
3 Correct 406 ms 36232 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 173 ms 20172 KB Output is correct
3 Correct 91 ms 24488 KB Output is correct
4 Correct 441 ms 36292 KB Output is correct
5 Correct 398 ms 36244 KB Output is correct
6 Correct 441 ms 36260 KB Output is correct
7 Correct 446 ms 36236 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Output is correct
2 Correct 7 ms 12620 KB Output is correct
3 Correct 91 ms 19144 KB Output is correct
4 Correct 85 ms 24392 KB Output is correct
5 Correct 157 ms 30888 KB Output is correct
6 Correct 161 ms 30804 KB Output is correct
7 Correct 175 ms 30840 KB Output is correct
8 Correct 165 ms 30748 KB Output is correct
9 Correct 153 ms 30768 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12592 KB Output is correct
2 Correct 7 ms 12492 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 8 ms 12620 KB Output is correct
5 Correct 9 ms 12772 KB Output is correct
6 Correct 414 ms 36240 KB Output is correct
7 Correct 404 ms 36472 KB Output is correct
8 Correct 406 ms 36232 KB Output is correct
9 Correct 7 ms 12620 KB Output is correct
10 Correct 173 ms 20172 KB Output is correct
11 Correct 91 ms 24488 KB Output is correct
12 Correct 441 ms 36292 KB Output is correct
13 Correct 398 ms 36244 KB Output is correct
14 Correct 441 ms 36260 KB Output is correct
15 Correct 446 ms 36236 KB Output is correct
16 Correct 7 ms 12492 KB Output is correct
17 Correct 7 ms 12620 KB Output is correct
18 Correct 91 ms 19144 KB Output is correct
19 Correct 85 ms 24392 KB Output is correct
20 Correct 157 ms 30888 KB Output is correct
21 Correct 161 ms 30804 KB Output is correct
22 Correct 175 ms 30840 KB Output is correct
23 Correct 165 ms 30748 KB Output is correct
24 Correct 153 ms 30768 KB Output is correct
25 Correct 7 ms 12492 KB Output is correct
26 Correct 96 ms 24484 KB Output is correct
27 Correct 176 ms 20184 KB Output is correct
28 Correct 398 ms 36212 KB Output is correct
29 Correct 439 ms 36172 KB Output is correct
30 Correct 398 ms 36236 KB Output is correct
31 Correct 403 ms 36164 KB Output is correct
32 Correct 430 ms 36188 KB Output is correct