Submission #1030176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030176		mdn2002	Distributing Candies (IOI21_candies)	C++17	8 / 100	1621 ms	1751124 KiB

candies

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

struct Node {
    long long mn = 0, mx = 0, lazy = 0;
    int left = -1, right = -1;
    Node() {}
};
Node st[55000006];
int cnt;
void push(int node, int l, int r) {
    st[node].mn += st[node].lazy;
    st[node].mx += st[node].lazy;
    if (l != r) {
        int left = st[node].left, right = st[node].right;
        st[left].lazy += st[node].lazy;
        st[right].lazy += st[node].lazy;
    }
    st[node].lazy = 0;
}
void update(int node, int l, int r, int x, int y, int val) {
    if (st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = Node();
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = Node();
    }
    push(node, l, r);
    if (x <= l && r <= y) {
        st[node].lazy += val;
        push(node, l, r);
        return;
    }
    if (y < l || r < x) return;

    int mid = (l + r) / 2, left = st[node].left, right = st[node].right;
    update(left, l, mid, x, y, val);
    update(right, mid + 1, r, x, y, val);
    st[node].mn = min(st[left].mn, st[right].mn);
    st[node].mx = max(st[left].mx, st[right].mx);
}

pair<long long, long long> query(int node, int l, int r, int x, int y) {
    if (st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = Node();
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = Node();
    }
    push(node, l, r);
    if (x <= l && r <= y) return {st[node].mn, st[node].mx};
    if (y < l || r < x) return {1e16, -1e16};
    int mid = (l + r) / 2;
    auto lc = query(st[node].left, l, mid, x, y);
    auto rc = query(st[node].right, mid + 1, r, x, y);
    return {min(lc.first, rc.first), max(lc.second, rc.second)};
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), m = l.size();
    vector<vector<pair<int, int>>> ql(n + 1), qr(n + 1);
    for (int i = 0; i < m; i ++) {
        ql[l[i]].push_back({v[i], i + 1});
        qr[r[i]].push_back({v[i], i + 1});
    }
    st[0] = Node();
    vector<int> s(n);
    for (int i = 0; i < n; i ++) {
        for (auto [v, j] : ql[i]) update(0, 0, m, j, m, v);
        int l = 0, r = m + 1, mid;
        while (l < r) {
            mid = (l + r) / 2;
            auto xx = query(0, 0, m, mid, m);
            if (xx.second - xx.first <= c[i]) r = mid;
            else l = mid + 1;
        }
        auto xx = query(0, 0, m, l, m);
        auto zz = query(0, 0, m, m, m);
        if (l == 0) s[i] = zz.first;
        else {
            if (v[l - 1] <= 0) s[i] = xx.first - zz.first;
            else s[i] = zz.second - (xx.second - c[i]);
        }
        for (auto [v, j] : qr[i]) update(0, 0, m, j, m, -v);
    }
    return s;
}
/*
3
10 15 13
2
0 2 10
0 1 1
*/

• Subtask 1: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33