oj.uz

Submission #597340

# Submission time Handle Problem Language Result Execution time Memory
597340 2022-07-15T22:45:48 Z skittles1412 Distributing Candies (IOI21_candies) C++17
100 / 100
 1012 ms 75988 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) {
        int y = max(0, x);
        return {y, y, x, y};
    }
};

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) {
        if (l > r) {
            return Node::from(0);
        }
        return query(1, 0, n - 1, l, r);
    }

    int bsearch1(int x) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (query(mid, n - 1).v < x) {
                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.bsearch1(arr[i]), negi = neg.bsearch1(arr[i]);
        dbg(posi, negi);
        if (posi == negi) {
            assert(!posi);
        }
        if (posi > negi) {
            ans[i] = arr[i] - neg.query(posi, q - 1).suff;
        } else {
            ans[i] = pos.query(negi, q - 1).suff;
        }
    }
    return ans;
}

Subtask #1
3.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 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 4 ms 980 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 69184 KB Output is correct
2 Correct 947 ms 70372 KB Output is correct
3 Correct 1012 ms 70324 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 369 ms 59632 KB Output is correct
3 Correct 245 ms 8644 KB Output is correct
4 Correct 1002 ms 69212 KB Output is correct
5 Correct 833 ms 75468 KB Output is correct
6 Correct 686 ms 75988 KB Output is correct
7 Correct 897 ms 75348 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 132 ms 58448 KB Output is correct
4 Correct 157 ms 7944 KB Output is correct
5 Correct 520 ms 65300 KB Output is correct
6 Correct 460 ms 69436 KB Output is correct
7 Correct 350 ms 70064 KB Output is correct
8 Correct 528 ms 68704 KB Output is correct
9 Correct 729 ms 70204 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 0 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 966 ms 69184 KB Output is correct
7 Correct 947 ms 70372 KB Output is correct
8 Correct 1012 ms 70324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 369 ms 59632 KB Output is correct
11 Correct 245 ms 8644 KB Output is correct
12 Correct 1002 ms 69212 KB Output is correct
13 Correct 833 ms 75468 KB Output is correct
14 Correct 686 ms 75988 KB Output is correct
15 Correct 897 ms 75348 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 132 ms 58448 KB Output is correct
19 Correct 157 ms 7944 KB Output is correct
20 Correct 520 ms 65300 KB Output is correct
21 Correct 460 ms 69436 KB Output is correct
22 Correct 350 ms 70064 KB Output is correct
23 Correct 528 ms 68704 KB Output is correct
24 Correct 729 ms 70204 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 191 ms 9216 KB Output is correct
27 Correct 354 ms 62232 KB Output is correct
28 Correct 854 ms 73744 KB Output is correct
29 Correct 797 ms 74120 KB Output is correct
30 Correct 744 ms 74304 KB Output is correct
31 Correct 704 ms 74620 KB Output is correct
32 Correct 673 ms 74580 KB Output is correct