Submission #609652

#	Time	Username	Problem	Language	Result	Execution time	Memory
609652		dxz05	Distributing Candies (IOI21_candies)	C++17	0 / 100	119 ms	51296 KiB

candies

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

using namespace std;
typedef long long ll;

ll C;

struct SegTree{
    struct node{
        ll min;
        ll max;
        ll add;
        node(){
            min = max = add = 0;
        }
    };

    int size;
    vector<node> t;

    SegTree(int n){
        size = n;
        t.assign(4 * n + 2, node());
    }

    void push(int v){
        if (t[v].add == 0) return;

        t[v << 1].min += t[v].add;
        t[v << 1].max += t[v].add;
        t[v << 1].add += t[v].add;

        t[v << 1 | 1].min += t[v].add;
        t[v << 1 | 1].max += t[v].add;
        t[v << 1 | 1].add += t[v].add;

        t[v].add = 0;
    }

    void update(int v, int tl, int tr, int l, int r, int x){
        if (l <= tl && tr <= r){
            if (x > 0){
                if (t[v].max + x <= C){
                    t[v].min += x;
                    t[v].max += x;
                    t[v].add += x;
                    return;
                }
            } else {
                if (t[v].min + x >= 0) {
                    t[v].min += x;
                    t[v].max += x;
                    t[v].add += x;
                    return;
                }
            }
        }
        if (tl > r || tr < l) return;

        push(v);

        int tm = (tl + tr) >> 1;

        update(v << 1, tl, tm, l, r, x);
        update(v << 1 | 1, tm + 1, tr, l, r, x);
        
        t[v].min = min(t[v << 1].min, t[v << 1 | 1].min);
        t[v].max = max(t[v << 1].max, t[v << 1 | 1].max);
    }

    int get(int v, int tl, int tr, int pos){
        if (tl == tr) return t[v].min;
        push(v);
        int tm = (tl + tr) >> 1;
        if (pos <= tm){
            return get(v << 1, tl, tm, pos);
        } else {
            return get(v << 1 | 1, tm + 1, tr, pos);
        }
    }

    void update(int l, int r, int x){
        update(1, 0, size - 1, l, r, x);
    }

    int get(int pos){
        return get(1, 0, size - 1, pos);
    }

};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    C = c[0];

    SegTree st(n);

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

    vector<int> ans(n, 2);
    for (int i = 0; i < n; i++) ans[i] = st.get(i);

    return ans;
}

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