oj.uz

Submission #621511

# Submission time Handle Problem Language Result Execution time Memory
621511 2022-08-03T23:39:29 Z resting Distributing Candies (IOI21_candies) C++17
100 / 100
 549 ms 69620 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 62960 KB Output is correct
2 Correct 462 ms 66904 KB Output is correct
3 Correct 476 ms 66816 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 314 ms 56280 KB Output is correct
3 Correct 69 ms 10028 KB Output is correct
4 Correct 460 ms 68828 KB Output is correct
5 Correct 549 ms 69172 KB Output is correct
6 Correct 510 ms 69620 KB Output is correct
7 Correct 429 ms 68952 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 109 ms 52648 KB Output is correct
4 Correct 63 ms 7904 KB Output is correct
5 Correct 189 ms 59520 KB Output is correct
6 Correct 192 ms 60144 KB Output is correct
7 Correct 184 ms 59980 KB Output is correct
8 Correct 204 ms 60100 KB Output is correct
9 Correct 182 ms 61324 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 454 ms 62960 KB Output is correct
7 Correct 462 ms 66904 KB Output is correct
8 Correct 476 ms 66816 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 314 ms 56280 KB Output is correct
11 Correct 69 ms 10028 KB Output is correct
12 Correct 460 ms 68828 KB Output is correct
13 Correct 549 ms 69172 KB Output is correct
14 Correct 510 ms 69620 KB Output is correct
15 Correct 429 ms 68952 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 109 ms 52648 KB Output is correct
19 Correct 63 ms 7904 KB Output is correct
20 Correct 189 ms 59520 KB Output is correct
21 Correct 192 ms 60144 KB Output is correct
22 Correct 184 ms 59980 KB Output is correct
23 Correct 204 ms 60100 KB Output is correct
24 Correct 182 ms 61324 KB Output is correct
25 Correct 1 ms 256 KB Output is correct
26 Correct 69 ms 9072 KB Output is correct
27 Correct 314 ms 56016 KB Output is correct
28 Correct 484 ms 67416 KB Output is correct
29 Correct 454 ms 67788 KB Output is correct
30 Correct 504 ms 68064 KB Output is correct
31 Correct 493 ms 68244 KB Output is correct
32 Correct 460 ms 68340 KB Output is correct