Submission #1221153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221153		madamadam3	Distributing Candies (IOI21_candies)	C++20	0 / 100	5095 ms	20552 KiB

candies

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

using namespace std;

struct Node {
    int sum;
    int mn, mx;

    Node() : sum(0), mn(INT_MAX), mx(INT_MIN) {};
    Node(int s, int MN, int MX) : sum(s), mn(MN), mx(MX) {};
    Node(int v) : sum(v), mn(v), mx(v) {};
    Node(Node left, Node right) {
        sum = left.sum + right.sum;
        mn = min(left.mn, right.mn);
        mx = max(left.mx, right.mx);
    }
};

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

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

    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].mx += op;
        st[i].mn += 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].mn >= cap) return st[i];
        if (ql <= l && r <= qr && st[i].mx + qdelt <= cap) {
            apply_update(i, l, r, qdelt);
            return st[i];
        }
        if (l + 1 == r) {
            int nv = min(st[i].sum + qdelt, cap);
            return st[i] = Node(nv);
        }

        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].mx <= 0) return st[i];
        if (ql <= l && r <= qr && st[i].mn + 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);
        }

        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[0]);
    // 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: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33