제출 #533115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533115		VodkaInTheJar	사탕 분배 (IOI21_candies)	C++17	30 / 100	5050 ms	39896 KiB

candies

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

using namespace std;

const int maxn = 2e5 + 3;

struct node {
    int min_val, max_val, max_cap, min_cap;
    int lazy_add_val, lazy_set_val, lazy_add_cap, lazy_set_cap;
    node() {lazy_add_val = lazy_add_cap = 0, lazy_set_val = lazy_set_cap = -1;}
};

node tr[maxn * 4];
void merge(int v) {
    tr[v].min_val = min(tr[v * 2].min_val, tr[v * 2 + 1].min_val);
    tr[v].max_val = max(tr[v * 2].max_val, tr[v * 2 + 1].max_val);
    tr[v].min_cap = min(tr[v * 2].min_cap, tr[v * 2 + 1].min_cap);
    tr[v].max_cap = max(tr[v * 2].max_cap, tr[v * 2 + 1].max_cap);
}

int arr[maxn];
void build(int v, int l, int r) {
    if (l == r) {
        tr[v].min_val = tr[v].max_val = 0;
        tr[v].min_cap = tr[v].max_cap = arr[l];

        return;
    }

    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);

    merge(v);
}

void push(int v, int l, int r) {
    if (tr[v].lazy_set_val != -1) {
        tr[v].min_val = tr[v].max_val = tr[v].lazy_set_val;
        if (l != r) {
            tr[v * 2].lazy_set_val = tr[v * 2 + 1].lazy_set_val = tr[v].lazy_set_val;
            tr[v * 2].lazy_add_val = tr[v * 2 + 1].lazy_add_val = 0;
        }
    }

    tr[v].min_val += tr[v].lazy_add_val, tr[v].max_val += tr[v].lazy_add_val;
    if (l != r)
        tr[v * 2].lazy_add_val += tr[v].lazy_add_val, tr[v * 2 + 1].lazy_add_val += tr[v].lazy_add_val;

    if (tr[v].lazy_set_cap != -1) {
        tr[v].min_cap = tr[v].max_cap = tr[v].lazy_set_cap;
        if (l != r) {
            tr[v * 2].lazy_set_cap = tr[v * 2 + 1].lazy_set_cap = tr[v].lazy_set_cap;
            tr[v * 2].lazy_add_cap = tr[v * 2 + 1].lazy_add_cap = 0;
        }
    }

    tr[v].min_cap += tr[v].lazy_add_cap, tr[v].max_cap += tr[v].lazy_add_cap;
    if (l != r)
        tr[v * 2].lazy_add_cap += tr[v].lazy_add_cap, tr[v * 2 + 1].lazy_add_cap += tr[v].lazy_add_cap;

    tr[v].lazy_add_cap = tr[v].lazy_add_val = 0;
    tr[v].lazy_set_cap = tr[v].lazy_set_val = -1;
}

void add_range(int v, int l, int r, int ll, int rr, int x) {
    push(v, l, r);
    if (l > rr || r < ll)
        return;

    int mid = (l + r) / 2;
    if (l >= ll && r <= rr) {
        if (tr[v].min_cap >= x) {
            tr[v].lazy_add_val += x;
            tr[v].lazy_add_cap -= x;
            push(v, l, r);

            return;
        }

        if (tr[v].max_cap < x) {
            if (tr[v].min_cap == tr[v].max_cap) {
                tr[v].lazy_add_val += tr[v].min_cap;
                tr[v].lazy_set_cap = 0;
                push(v, l, r);

                return;
            }
        }
    }

    add_range(v * 2, l, mid, ll, rr, x);
    add_range(v * 2 + 1, mid + 1, r, ll, rr, x);

    merge(v);
}

void sub_range(int v, int l, int r, int ll, int rr, int x) {
    push(v, l, r);
    if (l > rr || r < ll)
        return;

    int mid = (l + r) / 2;
    if (l >= ll && r <= rr) {
        if (tr[v].min_val >= x) {
            tr[v].lazy_add_val -= x;
            tr[v].lazy_add_cap += x;
            push(v, l, r);

            return;
        }

        if (tr[v].max_val < x) {
            if (tr[v].min_val == tr[v].max_val) {
                tr[v].lazy_add_cap += tr[v].min_val;
                tr[v].lazy_set_val = 0;
                push(v, l, r);

                return;
            }
        }
    }

    sub_range(v * 2, l, mid, ll, rr, x);
    sub_range(v * 2 + 1, mid + 1, r, ll, rr, x);

    merge(v);
}

int get(int v, int l, int r, int pos) {
    push(v, l, r);
    if (l == r)
        return tr[v].min_val;

    int mid = (l + r) / 2;
    if (pos <= mid)
        return get(v * 2, l, mid, pos);

    else
        return get(v * 2 + 1, mid + 1, r, pos);
}

vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v) {
    int n = (int)c.size();
    for (int i = 1; i <= n; i++)
        arr[i] = c[i-1];

    build(1, 1, n);

    int q = (int)l.size();
    for (int i = 0; i < q; i++) {
        if (v[i] > 0)
            add_range(1, 1, n, l[i] + 1, r[i] + 1, v[i]);

        else
            sub_range(1, 1, n, l[i] + 1, r[i] + 1, -v[i]);
    }

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

    return ans;
}

/*
int main() {
    int n, q;
    cin >> n >> q;
    vector <int> c(n), l(q), r(q), v(q);
    for (int i = 0; i < n; i++)
        cin >> c[i];

    for (int i = 0; i < q; i++)
        cin >> l[i] >> r[i] >> v[i];

    auto ans = distribute_candies(c, l, r, v);
    for (auto i: ans)
        cout << i << " ";
    cout << endl;
}

 */

/*
3 2
10 15 13
0 2 20
0 1 -11
 */

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