oj.uz

Submission #597243

# Submission time Handle Problem Language Result Execution time Memory
597243 2022-07-15T19:10:13 Z skittles1412 Distributing Candies (IOI21_candies) C++17
8 / 100
 1081 ms 74032 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct Node {
    long pref, suff, sum, v;

    Node operator+(const Node& n) const {
        return {max(pref, sum + n.pref), max(n.suff, suff + n.sum), sum + n.sum,
                max({v, n.v, suff + n.pref})};
    }

    static Node from(int x) {
        return {x, x, x, x};
    }
};

struct DS {
    int n;
    vector<Node> v;

    DS(int n) : n(n), v(4 * n, Node::from(0)) {}

    void update(int o, int l, int r, int ind, int x) {
        if (l == r) {
            v[o] = Node::from(x);
        } else {
            int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
            if (ind <= mid) {
                update(lc, l, mid, ind, x);
            } else {
                update(rc, mid + 1, r, ind, x);
            }
            v[o] = v[lc] + v[rc];
        }
    }

    void set(int ind, int x) {
        update(1, 0, n - 1, ind, x);
    }

    Node query(int o, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return v[o];
        } else {
            int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
            if (ql <= mid) {
                if (mid < qr) {
                    return query(lc, l, mid, ql, qr) +
                           query(rc, mid + 1, r, ql, qr);
                }
                return query(lc, l, mid, ql, qr);
            } else {
                return query(rc, mid + 1, r, ql, qr);
            }
        }
    }

    Node query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    long sum(int l, int r) {
        if (l > r) {
            return 0;
        }
        return query(l, r).sum;
    }

    template <typename T>
    int bsearchl(int ql, const T& t) {
        int l = ql, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (t(query(mid, n - 1))) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

vector<int> distribute_candies(vector<int> arr,
                               vector<int> ql,
                               vector<int> qr,
                               vector<int> qv) {
    int n = sz(arr), q = sz(ql);
    vector<pair<int, int>> upds[n + 1];
    for (int i = 0; i < q; i++) {
        upds[ql[i]].emplace_back(i, qv[i]);
        upds[qr[i] + 1].emplace_back(i, 0);
    }
    DS pos(q), neg(q);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        for (auto& [ind, x] : upds[i]) {
            pos.set(ind, x);
            neg.set(ind, -x);
        }
        int posi = pos.bsearchl(0, [&](const Node& n) -> bool {
            return n.v < arr[i];
        });
        int negi = neg.bsearchl(0, [&](const Node& n) -> bool {
            return n.v < arr[i];
        });
        dbg(posi, negi);
        if (posi == negi) {
            assert(!posi);
        }
        if (posi > negi) {
            int cl = pos.bsearchl(posi, [&](const Node& n) -> bool {
                return n.pref <= 0;
            });
            ans[i] = arr[i] + pos.sum(cl, q - 1);
        } else {
            int cl = neg.bsearchl(negi, [&](const Node& n) -> bool {
                return n.pref <= 0;
            });
            ans[i] = pos.sum(cl, q - 1);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 74032 KB Output is correct
2 Correct 1081 ms 73252 KB Output is correct
3 Correct 1079 ms 73080 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 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 0 ms 212 KB Output is correct
3 Incorrect 3 ms 852 KB Output isn't correct
4 Halted 0 ms 0 KB -