oj.uz

Submission #580548

# Submission time Handle Problem Language Result Execution time Memory
580548 2022-06-21T12:09:30 Z KoD Distributing Candies (IOI21_candies) C++17
100 / 100
 392 ms 36336 KB 
#include "candies.h"
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

struct info {
    ll sum, min, max;
};

constexpr info unit = {0, 0, 0};

info merge(const info& l, const info& r) {
    return {l.sum + r.sum, std::min(l.min, l.sum + r.min), std::max(l.max, l.sum + r.max)};
}

struct segtree {
    int size, logn;
    vector<info> data;
    explicit segtree(const int n) {
        logn = 0;
        while ((1 << logn) < n) logn += 1;
        size = 1 << logn;
        data.resize(2 * size, unit);
    }

    void set(int i, const info& o) {
        i += size;
        data[i] = o;
        while (i > 1) {
            i >>= 1;
            data[i] = merge(data[2 * i], data[2 * i + 1]);
        }
    }

    info prod(int l, int r) const {
        l += size;
        r += size;
        info sl = unit, sr = unit;
        while (l < r) {
            if (l & 1) sl = merge(sl, data[l++]);
            if (r & 1) sr = merge(data[--r], sr);
            l >>= 1;
            r >>= 1;
        }
        return merge(sl, sr);
    }

    info prod() const {
        return data[1];
    }

    template <class F>
    pair<int, info> min_left(const F& f) const {
        if (f(data[1])) {
            return {0, data[1]};
        }
        info acc = unit;
        int k = 1;
        while (k < size) {
            const int r = 2 * k + 1;
            if (f(merge(data[r], acc))) {
                acc = merge(data[r], acc);
                k <<= 1;
            } else {
                k = r;
            }
        }
        return {k - size + 1, acc};
    }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    const int N = C.size();
    const int Q = L.size();
    vector<vector<int>> enable(N), disable(N);
    for (int i = 0; i < Q; ++i) {
        enable[L[i]].push_back(i);
        disable[R[i]].push_back(i);
    }
    segtree seg(Q);
    vector<int> res(N);
    for (int i = 0; i < N; ++i) {
        for (const int q : enable[i]) {
            seg.set(q, {V[q], std::min(0, V[q]), std::max(0, V[q])});
        }
        const auto [l, acc] = seg.min_left([&](const info& x) {
            return x.max - x.min < C[i];
        });
        const auto all = seg.prod();
        if (l == 0) {
            res[i] = all.sum - all.min;
        } else if (V[l - 1] > 0) {
            const ll high = seg.prod(0, l).sum + acc.max;
            res[i] = C[i] - (high - all.sum); 
        } else {
            const ll low = seg.prod(0, l).sum + acc.min;
            res[i] = all.sum - low;
        }
        for (const int q : disable[i]) {
            seg.set(q, unit);
        }
    }
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 480 KB Output is correct
5 Correct 3 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 36256 KB Output is correct
2 Correct 359 ms 36172 KB Output is correct
3 Correct 373 ms 36244 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 157 ms 20312 KB Output is correct
3 Correct 108 ms 12224 KB Output is correct
4 Correct 347 ms 36244 KB Output is correct
5 Correct 335 ms 36200 KB Output is correct
6 Correct 386 ms 36328 KB Output is correct
7 Correct 328 ms 36248 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 340 KB Output is correct
3 Correct 107 ms 19228 KB Output is correct
4 Correct 76 ms 12096 KB Output is correct
5 Correct 163 ms 30856 KB Output is correct
6 Correct 186 ms 30800 KB Output is correct
7 Correct 182 ms 30800 KB Output is correct
8 Correct 161 ms 30764 KB Output is correct
9 Correct 185 ms 30884 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 480 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 392 ms 36256 KB Output is correct
7 Correct 359 ms 36172 KB Output is correct
8 Correct 373 ms 36244 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 157 ms 20312 KB Output is correct
11 Correct 108 ms 12224 KB Output is correct
12 Correct 347 ms 36244 KB Output is correct
13 Correct 335 ms 36200 KB Output is correct
14 Correct 386 ms 36328 KB Output is correct
15 Correct 328 ms 36248 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 107 ms 19228 KB Output is correct
19 Correct 76 ms 12096 KB Output is correct
20 Correct 163 ms 30856 KB Output is correct
21 Correct 186 ms 30800 KB Output is correct
22 Correct 182 ms 30800 KB Output is correct
23 Correct 161 ms 30764 KB Output is correct
24 Correct 185 ms 30884 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 62 ms 12244 KB Output is correct
27 Correct 146 ms 20268 KB Output is correct
28 Correct 325 ms 36336 KB Output is correct
29 Correct 365 ms 36252 KB Output is correct
30 Correct 367 ms 36324 KB Output is correct
31 Correct 349 ms 36200 KB Output is correct
32 Correct 338 ms 36152 KB Output is correct