Submission #1309921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309921		michael12	Distributing Candies (IOI21_candies)	C++20	0 / 100	224 ms	20768 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

struct segtree {
    struct Node {
        int val = 0;
        int mn = 0;  
        int mx = 0;  
        int lazy = 0;
    };
    
    vector<Node> tree;
    int n;
    vector<int> limit;

    segtree(int n, const vector<int>& c) : n(n), limit(c) {
        tree.resize(4 * n);
    }

    void push(int node, int start, int end) {
        if(tree[node].lazy != 0) {
            tree[node].val += tree[node].lazy;
            tree[node].mn += tree[node].lazy;
            tree[node].mx += tree[node].lazy;

            if(start != end) {
                tree[2*node].lazy += tree[node].lazy;
                tree[2*node+1].lazy += tree[node].lazy;
            }

            tree[node].lazy = 0;
        }

        if(start == end) {
            tree[node].val = max(0, min(tree[node].val, limit[start]));
            tree[node].mn = tree[node].val;
            tree[node].mx = tree[node].val;
        } else {
            tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
            tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
        }
    }

    void update(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if(start > r || end < l) return;

        if(l <= start && end <= r) {
            tree[node].lazy += val;
            push(node, start, end);
            if(tree[node].mn < 0 || tree[node].mx > limit[start]) {
                if(start != end) {
                    push(2*node, start, (start+end) / 2);
                    push(2*node+1, (start+end) / 2 + 1, end);
                }
            }
            return;
        }

        int mid = (start + end) / 2;
        update(2*node, start, mid, l, r, val);
        update(2*node+1, mid+1, end, l, r, val);

        tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
        tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
    }

    int get(int node, int start, int end, int id) {
        push(node, start, end);
        if(start == end) return tree[node].val;
        int mid = (start + end) / 2;
        if(id <= mid) return get(2*node, start, mid, id);
        else return get(2*node+1, mid+1, end, id);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    int sz = c.size();
    segtree ST(sz, c);
    for(int i = 0; i < v.size(); i++){
        ST.update(1, 0, sz-1, l[i], r[i], v[i]);
    }
    vector<int> ans(sz);
    for(int i = 0; i < sz; i++){
        ans[i] = ST.get(1, 0, sz-1, i);
    }
    return ans;
}

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