oj.uz

Submission #597285

# Submission time Handle Problem Language Result Execution time Memory
597285 2022-07-15T20:39:19 Z skittles1412 Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 71464 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;
    }

    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;
    }

    int nxt(int ql) {
        int l = ql - 1, r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (query(ql, mid).pref <= 0) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r + 2;
    }

    int nxt2(int x) {
        while (true) {
            int y = nxt(x);
            if (y > n) {
                return x;
            }
            x = y;
        }
    }
};

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] + pos.sum(pos.nxt2(posi), q - 1);
        } else {
            ans[i] = pos.sum(neg.nxt2(negi), q - 1);
        }
    }
    return ans;
}

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 3 ms 952 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 14 ms 1008 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5015 ms 69828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1154 ms 61936 KB Output is correct
3 Correct 1583 ms 10828 KB Output is correct
4 Execution timed out 5028 ms 71464 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 539 ms 60744 KB Output is correct
4 Correct 3775 ms 9156 KB Output is correct
5 Execution timed out 5019 ms 67512 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
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 3 ms 952 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 14 ms 1008 KB Output is correct
6 Execution timed out 5015 ms 69828 KB Time limit exceeded
7 Halted 0 ms 0 KB -