oj.uz

Submission #626652

# Submission time Handle Problem Language Result Execution time Memory
626652 2022-08-11T15:30:48 Z tabr Distributing Candies (IOI21_candies) C++17
100 / 100
 1311 ms 33440 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

// editorial

struct segtree {
    using T = pair<long long, long long>;
    using F = long long;

    T e() {
        return make_pair((long long) 1e18, (long long) -1e18);
    }

    F id() {
        return 0;
    }

    T op(T a, T b) {
        a.first = min(a.first, b.first);
        a.second = max(a.second, b.second);
        return a;
    }

    T mapping(F f, T x) {
        x.first += f;
        x.second += f;
        return x;
    }

    F composition(F f, F g) {
        return f + g;
    }

    int n;
    int size;
    int log_size;
    vector<T> node;
    vector<F> lazy;

    segtree() : segtree(0) {}
    segtree(int _n) {
        build(vector<T>(_n, e()));
    }
    segtree(const vector<T>& v) {
        build(v);
    }

    void build(const vector<T>& v) {
        n = (int) v.size();
        if (n <= 1) {
            log_size = 0;
        } else {
            log_size = 32 - __builtin_clz(n - 1);
        }
        size = 1 << log_size;
        node.resize(2 * size, e());
        lazy.resize(size, id());
        for (int i = 0; i < n; i++) {
            node[i + size] = v[i];
        }
        for (int i = size - 1; i > 0; i--) {
            pull(i);
        }
    }

    void push(int x) {
        node[2 * x] = mapping(lazy[x], node[2 * x]);
        node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]);
        if (2 * x < size) {
            lazy[2 * x] = composition(lazy[x], lazy[2 * x]);
            lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]);
        }
        lazy[x] = id();
    }

    void pull(int x) {
        node[x] = op(node[2 * x], node[2 * x + 1]);
    }

    void set(int p, T v) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        node[p] = v;
        for (int i = 1; i <= log_size; i++) {
            pull(p >> i);
        }
    }

    T get(int p) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        return node[p];
    }

    T get(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        for (int i = log_size; i >= 1; i--) {
            if (((l >> i) << i) != l) {
                push(l >> i);
            }
            if (((r >> i) << i) != r) {
                push((r - 1) >> i);
            }
        }
        T vl = e();
        T vr = e();
        while (l < r) {
            if (l & 1) {
                vl = op(vl, node[l++]);
            }
            if (r & 1) {
                vr = op(node[--r], vr);
            }
            l >>= 1;
            r >>= 1;
        }
        return op(vl, vr);
    }

    void apply(int p, F f) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        node[p] = mapping(f, node[p]);
        for (int i = 1; i <= log_size; i++) {
            pull(p >> i);
        }
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        for (int i = log_size; i >= 1; i--) {
            if (((l >> i) << i) != l) {
                push(l >> i);
            }
            if (((r >> i) << i) != r) {
                push((r - 1) >> i);
            }
        }
        int ll = l;
        int rr = r;
        while (l < r) {
            if (l & 1) {
                node[l] = mapping(f, node[l]);
                if (l < size) {
                    lazy[l] = composition(f, lazy[l]);
                }
                l++;
            }
            if (r & 1) {
                r--;
                node[r] = mapping(f, node[r]);
                if (l < size) {
                    lazy[r] = composition(f, lazy[r]);
                }
            }
            l >>= 1;
            r >>= 1;
        }
        l = ll;
        r = rr;
        for (int i = 1; i <= log_size; i++) {
            if (((l >> i) << i) != l) {
                pull(l >> i);
            }
            if (((r >> i) << i) != r) {
                pull((r - 1) >> i);
            }
        }
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int) c.size();
    int q = (int) v.size();
    segtree seg(vector<pair<long long, long long>>(q + 1, make_pair(0LL, 0LL)));
    vector<vector<int>> events(n + 1);
    for (int i = 0; i < q; i++) {
        events[l[i]].emplace_back(i);
        events[r[i] + 1].emplace_back(i);
    }
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        for (int j : events[i]) {
            if (l[j] == i) {
                seg.apply(j + 1, q + 1, v[j]);
            } else {
                seg.apply(j + 1, q + 1, -v[j]);
            }
        }
        auto last = seg.get(q).first;
        int low = -1;
        int high = q;
        while (high - low > 1) {
            int mid = (high + low) >> 1;
            auto p = seg.get(mid, q);
            if (p.second - p.first <= c[i]) {
                high = mid;
            } else {
                low = mid;
            }
        }
        debug(low, seg.node[1]);
        if (low == -1) {
            res[i] = (int) (last - seg.node[1].first);
        } else {
            auto p = seg.get(low, q);
            auto now = seg.get(low).first;
            if (p.second == now) {
                res[i] = (int) (last - p.first);
            } else if (p.first == now) {
                res[i] = (int) (c[i] + last - p.second);
            } else {
                assert(false);
            }
        }
        res[i] = min(c[i], max(0, res[i]));
    }
    return res;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    debug(distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11}));
    debug(distribute_candies({10}, {0, 0}, {0, 0}, {-3, 12}));
    return 0;
}
#endif

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 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 6 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1055 ms 27904 KB Output is correct
2 Correct 1090 ms 31972 KB Output is correct
3 Correct 1147 ms 31812 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 276 ms 21336 KB Output is correct
3 Correct 289 ms 9888 KB Output is correct
4 Correct 1087 ms 33292 KB Output is correct
5 Correct 1064 ms 33332 KB Output is correct
6 Correct 1033 ms 33304 KB Output is correct
7 Correct 1108 ms 33296 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 2 ms 300 KB Output is correct
3 Correct 159 ms 20340 KB Output is correct
4 Correct 274 ms 8712 KB Output is correct
5 Correct 861 ms 27988 KB Output is correct
6 Correct 875 ms 28664 KB Output is correct
7 Correct 859 ms 26164 KB Output is correct
8 Correct 907 ms 27532 KB Output is correct
9 Correct 954 ms 29364 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 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 1055 ms 27904 KB Output is correct
7 Correct 1090 ms 31972 KB Output is correct
8 Correct 1147 ms 31812 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 276 ms 21336 KB Output is correct
11 Correct 289 ms 9888 KB Output is correct
12 Correct 1087 ms 33292 KB Output is correct
13 Correct 1064 ms 33332 KB Output is correct
14 Correct 1033 ms 33304 KB Output is correct
15 Correct 1108 ms 33296 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 300 KB Output is correct
18 Correct 159 ms 20340 KB Output is correct
19 Correct 274 ms 8712 KB Output is correct
20 Correct 861 ms 27988 KB Output is correct
21 Correct 875 ms 28664 KB Output is correct
22 Correct 859 ms 26164 KB Output is correct
23 Correct 907 ms 27532 KB Output is correct
24 Correct 954 ms 29364 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 285 ms 8804 KB Output is correct
27 Correct 323 ms 20904 KB Output is correct
28 Correct 1311 ms 32456 KB Output is correct
29 Correct 1145 ms 32852 KB Output is correct
30 Correct 1231 ms 33040 KB Output is correct
31 Correct 1160 ms 33236 KB Output is correct
32 Correct 1100 ms 33440 KB Output is correct