oj.uz

Submission #579057

# Submission time Handle Problem Language Result Execution time Memory
579057 2022-06-18T10:57:28 Z KoD Distributing Candies (IOI21_candies) C++17
11 / 100
 5000 ms 8936 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;

template <class F>
struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class T> class fenwick_tree {
    vector<T> data;

  public:
    explicit fenwick_tree(const int n) : data(n + 1) {}

    void add(int i, const T& x) {
        i += 1;
        while (i < (int)data.size()) {
            data[i] += x;
            i += i & -i;
        }
    }

    T pref(int i) const {
        T ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }

    T fold(const int l, const int r) const {
        return pref(r) - pref(l);
    }
};

struct func {
    int lb, ub, add;
    int eval(const int x) {
        return std::clamp(x, lb, ub) + add;
    }
};

constexpr func unit = {-infty<int>, infty<int>, 0};

func composition(const func& f, const func& g) {
    auto [l1, r1, a1] = f;
    auto [l2, r2, a2] = g;
    l2 -= a1;
    r2 -= a1;
    a2 += a1;
    if (r1 <= l2) return {l2, l2, a2};
    if (r2 <= l1) return {r2, r2, a2};
    return {std::max(l1, l2), std::min(r1, r2), a2}; 
}

class segtree {
    int size, logn;
    vector<func> data;

    void apply(const int k, const func& f) {
        data[k] = composition(data[k], f);
    }

    void flush(const int k) {
        apply(2 * k, data[k]);
        apply(2 * k + 1, data[k]);
        data[k] = unit;
    }

    void push(int k) {
        const int z = __builtin_ctz(k);
        for (int d = logn; d > z; --d) {
            flush(k >> d);
        }
    }

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

    void apply(int l, int r, const func& f) {
        l += size;
        r += size;
        push(l);
        push(r);
        while (l < r) {
            if (l & 1) apply(l++, f);
            if (r & 1) apply(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }

    func get(int k) {
        k += size;
        for (int d = logn; d > 0; --d) {
            flush(k >> d);
        }
        return data[k];
    }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    const int N = (int)C.size();   
    const int Q = (int)L.size();
    for (auto& x : R) x += 1;

    if (N <= 2000 and Q <= 2000) {
        vector<int> X(N);
        for (int q = 0; q < Q; ++q) {
            for (int i = L[q]; i < R[q]; ++i) {
                X[i] = std::clamp(X[i] + V[q], 0, C[i]);
            }
        }
        return X;
    }

    if (*std::min_element(V.begin(), V.end()) > 0) {
        fenwick_tree<ll> fen(N);
        for (int q = 0; q < Q; ++q) {
            fen.add(L[q], V[q]);
            fen.add(R[q], -V[q]);
        }
        vector<int> X(N);
        for (int i = 0; i < N; ++i) {
            const ll tmp = fen.pref(i + 1);
            X[i] = tmp >= C[i] ? C[i] : tmp;
        }
        return X;
    }

    if (std::count(C.begin(), C.end(), C[0]) == N) {
        segtree seg(N);
        for (int q = 0; q < Q; ++q) {
            seg.apply(L[q], R[q], {-V[q], C[0] - V[q], V[q]});
        }
        vector<int> X(N);
        for (int i = 0; i < N; ++i) {
            X[i] = seg.get(i).eval(0);
        }
        return X;
    }

    vector<ll> sum(Q + 1);
    std::map<int, pair<int, int>> last;
    const auto calc = [&](const int i, const int t) {
        const auto [s, x] = last.upper_bound(i)->second;
        return (x == 0 ? 0 : C[i]) + (sum[t] - sum[s]);
    };
    last[0] = {N, 0};
    for (int q = 0; q < Q; ++q) {
        sum[q + 1] = sum[q] + V[q];
        int ng = -1, ok = N;
        while (std::abs(ng - ok) > 1) {
            const int md = (ok + ng) / 2;
            const int val = calc(md, q + 1);
            if (val < 0 or C[md] < val) {
                ng = md;
            } else {
                ok = md;
            }
        }
        while (last.begin() -> first < ok) {
            last.erase(last.begin());
        }
        last[ok] = {q + 1, V[q] < 0};
    }
    vector<int> X(N);
    for (int i = 0; i < N; ++i) {
        X[i] = calc(i, Q);
    }
    return X;
}

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 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 8808 KB Output is correct
2 Correct 127 ms 8936 KB Output is correct
3 Correct 108 ms 8932 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 175 ms 5196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.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 Execution timed out 5051 ms 6508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
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 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 124 ms 8808 KB Output is correct
7 Correct 127 ms 8936 KB Output is correct
8 Correct 108 ms 8932 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 175 ms 5196 KB Output isn't correct
11 Halted 0 ms 0 KB -