Submission #1221911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221911		madamadam3	Distributing Candies (IOI21_candies)	C++20	3 / 100	5097 ms	27720 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

struct Node {
    int sum;       
    int lmin, lmax;        
    int umin, umax;      

    Node() : sum(0), lmin(INT_MAX), lmax(INT_MIN), umin(INT_MAX), umax(INT_MIN) {}
    Node(int val, int cap) : sum(val), lmin(val), lmax(val), umin(cap - val), umax(cap - val) {}

    Node(const Node& A, const Node& B) {
        sum  = A.sum + B.sum;
        lmin = min(A.lmin, A.lmin < INT_MAX ? B.lmin : INT_MAX);
        lmax = max(A.lmax, B.lmax);
        umin = min(A.umin, A.umin < INT_MAX ? B.umin : INT_MAX);
        umax = max(A.umax, B.umax);
    }
};

struct SegmentTree {
    int n; vector<int> arr, cap;
    vector<Node> st;
    vector<int> lazy;

    SegmentTree(int N, vector<int> &Cap) {
        n = N;
        cap = Cap;
        arr.assign(n, 0);
        st.assign(4*n, Node());
        lazy.assign(4*n, 0);
        build(0, 0, n);
    }

    Node build(int i, int l, int r) {
        if (l + 1 == r) return st[i] = Node(0, cap[l]);
        int m = l + (r - l) / 2;
        return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
    }

    void apply_update(int i, int l, int r, int op) {
        int length = r - l;

        lazy[i] += op;
        st[i].sum += op * length;
        st[i].lmin += op;
        st[i].lmax += op;

        st[i].umin -= op;
        st[i].umax -= op;
    }

    void push_down(int i, int l, int r) {
        int m = l + (r - l) / 2;
        apply_update(2 * i + 1, l, m, lazy[i]);
        apply_update(2 * i + 2, m, r, lazy[i]);
        lazy[i] = 0;
    }

    Node query(int i, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return Node();
        if (ql <= l && r <= qr) return st[i];

        push_down(i, l, r);
        int m = l + (r - l) / 2;
        return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
    }

    Node upd_increase(int i, int l, int r, int ql, int qr, int qdelt) {
        if (qr <= l || r <= ql) return st[i];
        if (st[i].umax <= 0) return st[i];
        if (ql <= l && r <= qr && st[i].umin - qdelt >= 0) {
            apply_update(i, l, r, qdelt);
            return st[i];
        }

        if (l + 1 == r) {
            int nv = min(st[i].sum + qdelt, cap[l]);
            return st[i] = Node(nv, cap[l]);
        }

        push_down(i, l, r);
        int m = l + (r - l) / 2;
        return st[i] = Node(upd_increase(2*i+1, l, m, ql, qr, qdelt), upd_increase(2*i+2, m, r, ql, qr, qdelt));
    }

   Node upd_decrease(int i, int l, int r, int ql, int qr, int qdelt) {
        if (qr <= l || r <= ql) return st[i];
        if (st[i].lmax <= 0) return st[i];
        if (ql <= l && r <= qr && st[i].lmin + qdelt >= 0) {
            apply_update(i, l, r, qdelt);
            return st[i];
        }
        if (l + 1 == r) {
            int nv = max(st[i].sum + qdelt, 0);
            return st[i] = Node(nv, cap[l]);
        }

        push_down(i, l, r);
        int m = l + (r - l) / 2;
        return st[i] = Node(upd_decrease(2*i+1, l, m, ql, qr, qdelt), upd_decrease(2*i+2, m, r, ql, qr, qdelt));
    }

    void update(int l, int r, int delta) {
        if (delta < 0) upd_decrease(0, 0, n, l, r, delta);
        else upd_increase(0, 0, n, l, r, delta);
    }

    int query(int k) {
        return query(0, 0, n, k,k+1).sum;
    }
};

struct slow {
    int n; vector<int> cap, arr;

    slow(int N, vector<int> &cp) {
        n = N;
        cap = cp;
        arr.assign(n, 0);
    }

    void upd_increase(int l, int r, int delt) {
        for (int i = l; i <= r; i++) {
            arr[i] = min(arr[i] + delt, cap[i]);
        }
    }

    void upd_decrease(int l, int r, int delt) {
        for (int i = l; i <= r; i++) {
            arr[i] = max(arr[i] + delt, 0);
        }
    }

    void update(int l, int r, int delt) {
        if (delt < 0) upd_decrease(l, r, delt);
        else upd_increase(l, r, delt);
    }

    int query(int k) {
        return arr[k];
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
    vector<int> s(n);

    auto st = SegmentTree(n, c);
    // auto sl = slow(n, c);

    for (int i = 0; i < q; i++) {
        st.update(l[i], r[i]+1, v[i]);
        // sl.update(l[i], r[i], v[i]);
    }

    for (int i = 0; i < n; i++) {
        s[i] = st.query(i);
        // cout << st.query(i) << " ";
    }
    // cout << "\n";
    // for (int i = 0; i < n; i++) {
    //     cout << sl.query(i) << " ";
    // }
    // cout << "\n";
    // s = sl.arr;
    return s;
}

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